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 (12)

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

This page was built for publication: Complexity of finding graph roots with girth conditions