Computing roots of graphs is hard

DOI10.1016/0166-218X(94)00023-9MaRDI QIDQ1336641zbMATH OpenFDO

Authors Rajeev Motwani, Madhu Sudan

Publication date 3 November 1994

Published in Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

undirected graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Computing square roots of graphs with low maximum degree
• scientific article; zbMATH DE number 6027233
• Algorithms for Square Roots of Graphs
• Bipartite roots of graphs
• Complexity of finding graph roots with girth conditions

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3192675 (Why is no real title available?)
• A criterion for planarity of the square of a graph
• Algorithms for Square Roots of Graphs
• Characterization of n-path graphs and of graphs having \(n\)-th root
• Finding EPS-graphs
• Locality in Distributed Graph Algorithms
• The square of every two-connected graph is Hamiltonian
• The square root of a digraph
• The square root of a graph

Cited in

(35)

• A good characterization of squares of strongly chordal split graphs
• Extremal graphs for the identifying code problem
• The complexity of Boolean matrix root computation
• Local-Global Phenomena in Graphs
• Finding cut-vertices in the square roots of a graph
• Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
• Clique complexes and graph powers
• Strongly simplicial vertices of powers of trees
• Exact leaf powers
• Complexity of finding graph roots with girth conditions
• A linear-time algorithm for finding a one-to-many 3-disjoint path cover in the cube of a connected graph
• The Clique-Width of Tree-Power and Leaf-Power Graphs
• Closest 4-leaf power is fixed-parameter tractable
• Strictly chordal graphs are leaf powers
• The NLC-width and clique-width for powers of graphs of bounded tree-width
• Linear-time algorithms for tree root problems
• Model checking on interpretations of classes of bounded local cliquewidth
• Computing square roots of trivially perfect and threshold graphs
• A characterization of line graphs that are squares of graphs
• scientific article; zbMATH DE number 6027233 (Why is no real title available?)
• Finding cactus roots in polynomial time
• scientific article; zbMATH DE number 15239 (Why is no real title available?)
• A linear kernel for finding square roots of almost planar graphs
• A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph
• Finding cactus roots in polynomial time
• A unified approach to recognize squares of split graphs
• Computing square roots of graphs with low maximum degree
• Biclique graphs of interval bigraphs
• Parameterized algorithms for finding square roots
• Squares of low clique number
• Structure of squares and efficient domination in graph classes
• Partial characterizations of 1-perfectly orientable graphs
• The complexity of Boolean matrix root computation
• Graph square roots of small distance from degree one graphs
• The square of a block graph

This page was built for publication: Computing roots of graphs is hard

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