Finding cactus roots in polynomial time

DOI10.1007/s00224-017-9825-2zbMath1391.68052OpenAlexW2769849834WikidataQ59603573 ScholiaQ59603573MaRDI QIDQ726100

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

Publication date: 3 August 2018

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-017-9825-2

zbMATH Keywords

treewidthclique numbersquare rootcactus

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 (4)

Sample Compression Schemes for Balls in Graphs ⋮ Finding cut-vertices in the square roots of a graph ⋮ Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2 ⋮ Graph square roots of small distance from degree one graphs

Cites Work

• Unnamed Item
• Parameterized algorithms for finding square roots
• A unified approach to recognize squares of split graphs
• 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
• Graph minors. XVI: Excluding a non-planar graph
• A good characterization of squares of strongly chordal split graphs
• A linear kernel for finding square roots of almost planar graphs
• Computing square roots of graphs with low maximum degree
• Complexity of finding graph roots with girth conditions
• Square roots of minor closed graph classes
• Computing square roots of trivially perfect and threshold graphs
• Finding Cactus Roots in Polynomial Time
• Linear Time Algorithm for Computing a Small Biclique in Graphs without Long Induced Paths
• 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 criterion for planarity of the square of a graph
• The square root of a graph
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Finding cut-vertices in the square roots of a graph
• Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2

This page was built for publication: Finding cactus roots in polynomial time