Algorithms for Square Roots of Graphs

DOI10.1137/S089548019120016XzbMATH Open0821.05052MaRDI QIDQ4764347FDOQ4764347

Authors: Yaw-Ling Lin, Steven Skiena 

Publication date: 4 May 1995

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Recommendations

• Computing roots of graphs is hard
• On tree roots of graphs
• Hardness Results and Efficient Algorithms for Graph Powers
• scientific article; zbMATH DE number 6027233

zbMATH Keywords

distanceNP-completenessplanar graphsquare rootHamilton cycleslinear time algorithmpowers of graphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45) Distance in graphs (05C12)

Cited In (42)

• Large-girth roots of graphs
• A characterization of line graphs that are squares of graphs
• Distance three labelings of trees
• Title not available (Why is that?)
• Parameterized algorithms for finding square roots
• Linear-time algorithms for tree root problems
• On the complexity of distance-\(d\) independent set reconfiguration
• The square of a block graph
• Exact leaf powers
• Computing roots of graphs is hard
• Square roots of minor closed graph classes
• Finding cactus roots in polynomial time
• Finding cactus roots in polynomial time
• The Clique-Width of Tree-Power and Leaf-Power Graphs
• Large-girth roots of graphs
• Optimal radiocoloring of trees
• Title not available (Why is that?)
• A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph
• The square root of a digraph
• Linear-time recognition of map graphs with outerplanar witness
• Closest 4-leaf power is fixed-parameter tractable
• On the complexity of distance-\(d\) independent set reconfiguration
• Complexity of finding graph roots with girth conditions
• The NLC-width and clique-width for powers of graphs of bounded tree-width
• Computing square roots of trivially perfect and threshold graphs
• Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
• Graph square roots of small distance from degree one graphs
• On the general position number of the k -th power graphs
• A linear kernel for finding square roots of almost planar graphs
• Computing square roots of graphs with low maximum degree
• On tree roots of graphs
• Finding cut-vertices in the square roots of a graph
• Fixed-parameter complexity of \(\lambda\)-labelings
• The clique number of the exact distance \(t\)-power graph: complexity and eigenvalue bounds
• Squares of low clique number
• A linear-time algorithm for finding a one-to-many 3-disjoint path cover in the cube of a connected graph
• Strictly chordal graphs are leaf powers
• Title not available (Why is that?)
• Radiocoloring in planar graphs: Complexity and approximations
• On powers of \(m\)-trapezoid graphs
• Complexity of the Packing Coloring Problem for Trees
• Biclique graphs of interval bigraphs

This page was built for publication: Algorithms for Square Roots of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4764347)