Finding cactus roots in polynomial time
DOI10.1007/S00224-017-9825-2zbMATH Open1391.68052OpenAlexW2769849834WikidataQ59603573 ScholiaQ59603573MaRDI QIDQ726100FDOQ726100
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)
Full work available at URL: https://doi.org/10.1007/s00224-017-9825-2
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph operations (line graphs, products, etc.) (05C76)
Cites Work
- Graph theory
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Computing roots of graphs is hard
- A good characterization of squares of strongly chordal split graphs
- Complexity of finding graph roots with girth conditions
- Computing square roots of trivially perfect and threshold graphs
- Parameterized algorithms for finding square roots
- Bipartite roots of graphs
- Recognizing Powers of Proper Interval, Split, and Chordal Graphs
- Algorithms for Square Roots of Graphs
- Uniqueness of graph square roots of girth six
- The square root of a graph
- The square of a block graph
- Linear time algorithm for computing a small biclique in graphs without long induced paths
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- A unified approach to recognize squares of split graphs
- Graph minors. XVI: Excluding a non-planar graph
- A characterization of line graphs that are squares of graphs
- Square roots of minor closed graph classes
- Squares of low clique number
- 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
- A criterion for planarity of the square of a graph
- Finding cut-vertices in the square roots of a graph
- Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
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
- Finding cut-vertices in the square roots of a graph
- Title not available (Why is that?)
- 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)
