Rooted cycle bases

DOI10.7155/JGAA.00434MaRDI QIDQ5278052zbMATH OpenOpenAlexFDO

Authors David Eppstein, J. Michael McCarthy, Brian E. Parrish

Publication date 13 July 2017

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1504.04931

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: A cycle basis in an undirected graph is a minimal set of simple cycles whose symmetric differences include all Eulerian subgraphs of the given graph. We define a rooted cycle basis to be a cycle basis in which all cycles contain a specified root edge, and we investigate the algorithmic problem of constructing rooted cycle bases. We show that a given graph has a rooted cycle basis if and only if the root edge belongs to its 2-core and the 2-core is 2-vertex-connected, and that constructing such a basis can be performed efficiently. We show that in an unweighted or positively weighted graph, it is possible to find the minimum weight rooted cycle basis in polynomial time. Additionally, we show that it is NP-complete to find a fundamental rooted cycle basis (a rooted cycle basis in which each cycle is formed by combining paths in a fixed spanning tree with a single additional edge) but that the problem can be solved by a fixed-parameter-tractable algorithm when parameterized by clique-width.

Recommendations

• Rooted cycle bases
• Minimum Cycle Bases in Graphs Algorithms and Applications
• Minimum Cycle Bases and Their Applications
• Minimum cycle bases, faster and simpler
• scientific article; zbMATH DE number 2080984

Cited in

(5)

• A note on fundamental, non-fundamental, and robust cycle bases
• The minimum rooted-cycle cover problem
• Rooted cycle bases
• Is every cycle basis fundamental?
• Classification of robust cycle bases and relations to fundamental cycle bases

This page was built for publication: Rooted cycle bases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5278052)