Computing roots of graphs is hard

DOI10.1016/0166-218X(94)00023-9zbMath0812.68103MaRDI QIDQ1336641

Madhu Sudan, Rajeev Motwani

Publication date: 3 November 1994

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

zbMATH Keywords

undirected graph

Mathematics Subject Classification ID

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

Related Items

Local-Global Phenomena in Graphs, Partial Characterizations of 1‐Perfectly Orientable Graphs, Finding cut-vertices in the square roots of a graph, Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2, Graph square roots of small distance from degree one graphs, Hardness and structural results for half-squares of restricted tree convex bipartite graphs, Parameterized algorithms for finding square roots, A unified approach to recognize squares of split graphs, Structure of squares and efficient domination in graph classes, Clique complexes and graph powers, A characterization of line graphs that are squares of graphs, Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs, Squares of low clique number, Finding cactus roots in polynomial time, A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph, Strictly chordal graphs are leaf powers, The square of a block graph, Exact leaf powers, Closest 4-leaf power is fixed-parameter tractable, The NLC-width and clique-width for powers of graphs of bounded tree-width, A linear-time algorithm for finding a one-to-many 3-disjoint path cover in the cube of a connected graph, The complexity of Boolean matrix root computation, A good characterization of squares of strongly chordal split graphs, Biclique graphs of interval bigraphs, Linear-time algorithms for tree root problems, A linear kernel for finding square roots of almost planar graphs, Computing square roots of graphs with low maximum degree, Complexity of finding graph roots with girth conditions, Extremal graphs for the identifying code problem, Computing square roots of trivially perfect and threshold graphs, Strongly simplicial vertices of powers of trees, Finding Cactus Roots in Polynomial Time, The Clique-Width of Tree-Power and Leaf-Power Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Finding EPS-graphs
• The square of every two-connected graph is Hamiltonian
• Characterization of n-path graphs and of graphs having \(n\)-th root
• Locality in Distributed Graph Algorithms
• Algorithms for Square Roots of Graphs
• A criterion for planarity of the square of a graph
• The square root of a graph
• The square root of a digraph