Algorithms for Square Roots of Graphs

DOI10.1137/S089548019120016XMaRDI QIDQ4764347zbMATH OpenFDO

Authors Yaw-Ling Lin, Steven Skiena

Publication date 4 May 1995

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

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)

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

Cited in

(42)

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

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)