Scholarlink

<p>Minimum spanning cactus and minimum spanning cactus extension problems on outerplanar graphs are studied. Linear algorithms are presented for both problems on outerplanar graphs. A partitioning technique is introduced that partitions a maximal biconnected outerplanar graph into a set of maximal star-outerplanar subgraphs and some chords. Further, the minimum spanning cacti of these star-outerplanar subgraphs can be computed and suitably combined to get a minimum spanning cactus and a minimum spanning cactus extension of a given outerplanar graph.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Spanning cactus and spanning cactus extension of outerplanar graphs

  • 期刊论文

  • 发表日期：

    2025年9月24日

查看全文
  • Chinmay Debnath,
  • Alak Kumar Datta

摘要

Minimum spanning cactus and minimum spanning cactus extension problems on outerplanar graphs are studied. Linear algorithms are presented for both problems on outerplanar graphs. A partitioning technique is introduced that partitions a maximal biconnected outerplanar graph into a set of maximal star-outerplanar subgraphs and some chords. Further, the minimum spanning cacti of these star-outerplanar subgraphs can be computed and suitably combined to get a minimum spanning cactus and a minimum spanning cactus extension of a given outerplanar graph.