Finding Cactus Roots in Polynomial Time

DOI10.1007/978-3-319-44543-4_28zbMath1391.68051OpenAlexW2567238621MaRDI QIDQ2819519

Anthony Stewart, Petr A. Golovach, Daniël Paulusma, Dieter Kratsch

Publication date: 29 September 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/19880/1/19880.pdf

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph operations (line graphs, products, etc.) (05C76)

Related Items

A linear kernel for finding square roots of almost planar graphs ⋮ Computing square roots of graphs with low maximum degree ⋮ Finding cactus roots in polynomial time ⋮ Parameterized leaf power recognition via embedding into graph products

Cites Work

• Unnamed Item
• Parameterized algorithms for finding square roots
• A characterization of line graphs that are squares of graphs
• Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs
• Squares of low clique number
• Uniqueness of graph square roots of girth six
• The square of a block graph
• Computing roots of graphs is hard
• A good characterization of squares of strongly chordal split graphs
• Complexity of finding graph roots with girth conditions
• Square roots of minor closed graph classes
• Computing square roots of trivially perfect and threshold graphs
• Sparse Square Roots
• Bipartite roots of graphs
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• Algorithms for Square Roots of Graphs
• A Linear Kernel for Finding Square Roots of Almost Planar Graphs
• Parameterized Algorithms
• The square root of a graph
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Finding Cactus Roots in Polynomial Time