scientific article; zbMATH DE number 2044511

MaRDI QIDQ4448375zbMATH OpenFDO

Authors André Große, Jörg Rothe, Gerd Wechsung

Publication date 18 February 2004

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2202/22020339.htm

zbMATH Keywords

Hamiltonian cyclesgraph colorabilityself-reducibilitygraph isomorphismspartial solutionscomplexity of smallest solutions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P
• Computing complete graph isomorphisms and Hamiltonian cycles from partial ones
• Planar graph coloring is not self-reducible, assuming P\(\neq NP\)
• Computing graph automorphism from partial solutions
• On the hardness of computing maximum self-reduction sequences

Cited in

(5)

• Relation between the hardness of a problem and the number of its solutions
• On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P
• Computing graph automorphism from partial solutions
• A new class of the smallest FSSP partial solutions for 1D rings of length \(n=2^k-1\)
• Shellings from relative shellings, with an application to NP-completeness

This page was built for publication:

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