A Polynomial Algorithm for Recognizing Perfect Graphs

Cambridge, Massachusettes October 11-October 14

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/SFCS.2003.1238177

44th Annual IEEE Symposium on Foundat ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Gérard Cornuéjols Articles by Xinming Liu Articles by Kristina Vušković

	ASCII Text	x
	Gérard Cornuéjols, Xinming Liu, Kristina Vušković, "A Polynomial Algorithm for Recognizing Perfect Graphs," Foundations of Computer Science, Annual IEEE Symposium on, pp. 20, 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03), 2003.

	BibTex	x
	@article{ 10.1109/SFCS.2003.1238177, author = {Gérard Cornuéjols and Xinming Liu and Kristina Vušković}, title = {A Polynomial Algorithm for Recognizing Perfect Graphs}, journal ={Foundations of Computer Science, Annual IEEE Symposium on}, volume = {0}, year = {2003}, issn = {0272-5428}, pages = {20}, doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2003.1238177}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Foundations of Computer Science, Annual IEEE Symposium on TI - A Polynomial Algorithm for Recognizing Perfect Graphs SN - 0272-5428 SP EP A1 - Gérard Cornuéjols, A1 - Xinming Liu, A1 - Kristina Vušković, PY - 2003 KW - perfect graph KW - odd hole KW - recognition algorithm KW - decomposition KW - cleaning VL - 0 JA - Foundations of Computer Science, Annual IEEE Symposium on ER -

Gérard Cornuéjols, Université de Marseille

Xinming Liu, Carnegie Mellon University

Kristina Vušković, University of Leeds

We present a polynomial algorithm for recognizing whether a graph is perfect, thus settling a long standing open question. The algorithm uses a decomposition theorem of Conforti, Cornuéjols and Vu?sković. Another polynomial algorithm for recognizing perfect graphs, which does not use decomposition, was obtained simultaneously by Chudnovsky and Seymour. Both algorithms need a first phase developed jointly by Chudnovsky, Cornuéjols, Liu, Seymour and Vu?sković.

Index Terms:

perfect graph, odd hole, recognition algorithm, decomposition, cleaning

Citation:

Gérard Cornuéjols, Xinming Liu, Kristina Vušković, "A Polynomial Algorithm for Recognizing Perfect Graphs," focs, pp.20, 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03), 2003

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.