The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem
From MaRDI portal
Publication:3323288
DOI10.1137/0213008zbMath0537.68067MaRDI QIDQ3323288
Publication date: 1984
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0213008
lower bound; acyclic orientation; decision tree; Hamiltonian path; vertex-coloring; element uniqueness
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C45: Eulerian and Hamiltonian graphs
Related Items
Acyclic orientations of random graphs, Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems, Elements of a theory of simulation. II: Sequential dynamical systems., Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph