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

Contractibility and NP-completeness

Share/Save/Bookmark

Brouwer, A.E. and Veldman, H.J. (1987) Contractibility and NP-completeness. Journal of Graph Theory, 11 (1). pp. 71-79. ISSN 0364-9024

[img]
Preview
PDF
328Kb
Abstract:For a fixed graph H, let H-CON denote the problem of determining whether a given graph is contractible to H. The complexity of H-CON is studied for H belonging to certain classes of graphs, together covering all connected graphs of order at most 4. In particular, H-CON is NP-complete if H is a connected triangle-free graph other than a star. For each connected graph H of order at most 4 other than P4 and C4, H-CON is solvable in polynomial time.
Item Type:Article
Copyright:© 1987 Wiley InterScience
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/70829
Official URL:http://dx.doi.org/10.1002/jgt.3190110111
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page