Home About Upload Latest Additions Statistics Contact
UT Proceedings
UT Student Theses
Dutch Academic Output Dutch Dissertations EU Publications (OpenAIRE)
Printversion
Advanced search

Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion

Share/Save/Bookmark

Bauer, D. and Broersma, H.J. and Morgana, A. and Schmeichel, E. (1999) Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion. [Report]

[img]
Preview
PDF
161Kb
Abstract: A number of results in Hamiltonian graph theory are of the form $\mathcal{P}$$_{1}$ implies $\mathcal{P}$$_{2}$, where $\mathcal{P}$$_{1}$ is a property of graphs that is NP-hard and $\mathcal{P}$$_{2}$ is a cycle structure property of graphs that is also NP-hard. Such a theorem is the well-known Chv\'{a}tal-Erd\"{o}s Theorem, which states that every graph $G$ with $\alpha \leq \kappa $ is Hamiltonian. Here $\kappa $ is the vertex connectivity of $G$ and $\alpha $ is the cardinality of a largest set of independent vertices of $G$. In another paper Chv\'{a}tal points out that the proof of this result is in fact a polynomial time construction that either produces a Hamilton cycle or a set of more than $\kappa $ independent vertices. In this note we point out that other theorems in Hamiltonian graph theory have a similar character. In particular, we present a constructive proof of the well-known theorem of Jung for graphs on $16$ or more vertices..
Item Type:Report
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/65687
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 141297