Complexity of finding graph roots with girth conditions

DOI10.1007/s00453-010-9442-9zbMath1239.05127OpenAlexW2062659098MaRDI QIDQ2428666

Lap Chi Lau, Babak Farzad, Nguyen Ngoc Tuy, Van Bang Le

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.318.8391

zbMATH Keywords

NP-completenessrecognition algorithmsgraph powersgraph roots

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

A linear kernel for finding square roots of almost planar graphs, Computing square roots of graphs with low maximum degree, Biclique graphs of interval bigraphs, A characterization of line graphs that are squares of graphs, Computing square roots of trivially perfect and threshold graphs, Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs, 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, Parameterized algorithms for finding square roots

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matrix multiplication via arithmetic progressions
• Choosability of the square of planar subcubic graphs with large girth
• Computing roots of graphs is hard
• Bipartite roots of graphs
• Minimum Edge Dominating Sets
• List-coloring the square of a subcubic graph
• A New Algorithm for Generating All the Maximal Independent Sets
• Finding a Minimum Circuit in a Graph
• Tree Powers
• The Chromatic Number of Graph Powers
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• Algorithms for Square Roots of Graphs
• Structure and linear-time recognition of 4-leaf powers
• The square root of a graph
• Linear-Time Algorithms for Tree Root Problems