Parameterized algorithms for finding square roots
From MaRDI portal
Publication:262249
DOI10.1007/s00453-014-9967-4zbMath1332.05136arXiv1310.5469OpenAlexW2111680439MaRDI QIDQ262249
Jean-François Couturier, Petr A. Golovach, Manfred Cochefert, Daniël Paulusma, Dieter Kratsch
Publication date: 29 March 2016
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1310.5469
Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) 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 ⋮ Maximizing the strong triadic closure in split graphs and proper interval graphs ⋮ Strong triadic closure in cographs and graphs of low maximum degree ⋮ Finding cut-vertices in the square roots of a graph ⋮ Finding cactus roots in polynomial time ⋮ Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2 ⋮ Graph square roots of small distance from degree one graphs ⋮ Finding Cactus Roots in Polynomial Time ⋮ Unnamed Item
Cites Work
- Fundamentals of parameterized complexity
- Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs
- Uniqueness of graph square roots of girth six
- Solving MAX-\(r\)-SAT above a tight lower bound
- 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
- Computing square roots of trivially perfect and threshold graphs
- Parametrized complexity theory.
- Sparse Square Roots
- Bipartite roots of graphs
- A New Algorithm for Generating All the Maximal Independent Sets
- Recognizing Powers of Proper Interval, Split, and Chordal Graphs
- Algorithms for Square Roots of Graphs
- The square root of a graph
- On cliques in graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
