Geodesic
Rooted Cycle Bases
Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 4, pp. 663-686.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00434
Keywords: cycle basis, ear decomposition, weighted undirected graph, Hamiltonian cycle, fixed-parameter tractability, Courcelle's theorem, incremental first difference problem 
@article{JGAA_2017_21_4_a12,
     author = {David Eppstein and J. Michael McCarthy and Brian Parrish},
     title = {Rooted {Cycle} {Bases}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {663--686},
     publisher = {mathdoc},
     volume = {21},
     number = {4},
     year = {2017},
     doi = {10.7155/jgaa.00434},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00434/}
}
TY  - JOUR
AU  - David Eppstein
AU  - J. Michael McCarthy
AU  - Brian Parrish
TI  - Rooted Cycle Bases
JO  - Journal of Graph Algorithms and Applications
PY  - 2017
SP  - 663
EP  - 686
VL  - 21
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00434/
DO  - 10.7155/jgaa.00434
LA  - en
ID  - JGAA_2017_21_4_a12
ER  - 
%0 Journal Article
%A David Eppstein
%A J. Michael McCarthy
%A Brian Parrish
%T Rooted Cycle Bases
%J Journal of Graph Algorithms and Applications
%D 2017
%P 663-686
%V 21
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00434/
%R 10.7155/jgaa.00434
%G en
%F JGAA_2017_21_4_a12
David Eppstein; J. Michael McCarthy; Brian Parrish. Rooted Cycle Bases. Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 4, pp. 663-686. doi : 10.7155/jgaa.00434. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00434/

Cité par Sources :