scientific article; zbMATH DE number 2044511
zbMATH Open1042.68605MaRDI QIDQ4448375FDOQ4448375
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
Title of this publication is not available (Why is that?)
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
Hamiltonian cyclesgraph colorabilityself-reducibilitygraph isomorphismspartial solutionscomplexity of smallest solutions
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)
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)
