Finding cactus roots in polynomial time

DOI10.1007/S00224-017-9825-2MaRDI QIDQ726100zbMATH OpenOpenAlexWikidataFDO

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

Publication date 3 August 2018

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

treewidthcactusclique numbersquare root

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)

Recommendations

• Finding cactus roots in polynomial time
• Polynomial Root-Finding Algorithms and Branched Covers
• Polynomial invariants for cactuses
• Finding polynomial roots: A fast algorithm convergent on the complex plane
• On the cost of computing roots of polynomials
• A polynomial algorithm for finding \(T\)-span of generalized cacti
• A linear algorithm for finding a minimum dominating set in a cactus
• Complexity of finding graph roots with girth conditions
• ON HIGHLY EFFICIENT SIMULTANEOUS SCHEMES FOR FINDING ALL POLYNOMIAL ROOTS

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A characterization of line graphs that are squares of graphs
• A criterion for planarity of the square of a graph
• A good characterization of squares of strongly chordal split graphs
• A linear kernel for finding square roots of almost planar graphs
• A unified approach to recognize squares of split graphs
• Algorithms for Square Roots of Graphs
• Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
• Bipartite roots of graphs
• Complexity of finding graph roots with girth conditions
• Computing roots of graphs is hard
• Computing square roots of graphs with low maximum degree
• Computing square roots of trivially perfect and threshold graphs
• Finding cactus roots in polynomial time
• Finding cut-vertices in the square roots of a graph
• Graph minors. XVI: Excluding a non-planar graph
• Graph theory
• Linear time algorithm for computing a small biclique in graphs without long induced paths
• Parameterized algorithms for finding square roots
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• Square roots of minor closed graph classes
• Squares of low clique number
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• The square of a block graph
• The square root of a graph
• Uniqueness of graph square roots of girth six

Cited in

(12)

• Sample Compression Schemes for Balls in Graphs
• Square roots of minor closed graph classes
• Finding cactus roots in polynomial time
• Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
• Finding cut-vertices in the square roots of a graph
• Sparse square roots
• Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
• Graph square roots of small distance from degree one graphs
• Computing square roots of graphs with low maximum degree
• scientific article; zbMATH DE number 3867373 (Why is no real title available?)
• Finding cut-vertices in the square roots of a graph
• Squares of low clique number

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

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