Graph square roots of small distance from degree one graphs

DOI10.1007/s00224-022-10079-8zbMath1493.05082OpenAlexW3092605452MaRDI QIDQ5918752

Petr A. Golovach, Charis Papadopoulos, Paloma T. Lima

Publication date: 26 July 2022

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

Full work available at URL: https://doi.org/10.1007/s00224-022-10079-8

zbMATH Keywords

vertex coversquare rootstructural parameterization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distance in graphs (05C12) Parameterized complexity, tractability and kernelization (68Q27)

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
• Finding cactus roots in polynomial time
• The square of a block graph
• An application of simultaneous diophantine approximation in combinatorial optimization
• Computing roots of graphs is hard
• Which problems have strongly exponential complexity?
• 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
• Bipartite roots of graphs
• Integer Programming with a Fixed Number of Variables
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Minkowski's Convex Body Theorem and Integer Programming
• Node-Deletion Problems on Bipartite Graphs
• On the Parameterized Complexity of Biclique Cover and Partition
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• Algorithms for Square Roots of Graphs
• Parameterized Algorithms
• Finding cut-vertices in the square roots of a graph
• Graph square roots of small distance from degree one graphs
• Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
• On the complexity of \(k\)-SAT

This page was built for publication: Graph square roots of small distance from degree one graphs