DSpace
 

EPrints@IIT Delhi >
Faculty Research Publicatons  >
Computer Science and Engineering >

Please use this identifier to cite or link to this item: http://eprint.iitd.ac.in/handle/2074/2507

Full metadata record

DC FieldValueLanguage
dc.contributor.authorVazirani, Vijay V-
dc.contributor.authorKhuller, Samir-
dc.date.accessioned2007-02-14T03:59:52Z-
dc.date.available2007-02-14T03:59:52Z-
dc.date.issued1991-
dc.identifier.citationTheoretical Computer Science, 88(1), 183-189p.en
dc.identifier.urihttp://eprint.iitd.ac.in/dspace/handle/2074/2507-
dc.description.abstractWe show that obtaining the lexicographically first four coloring of a planar graph is NP-hard. This shows that planar graph four-coloring is not self-reducible, assuming P≠ NP. One consequence of our result is that the schema of Jerrum et al. (1986) cannot be used for approximately counting the number of four colorings of a planar graph. These results extend to planar graph k-coloring, for k4.en
dc.format.extent150579 bytes-
dc.format.mimetypeapplication/pdf-
dc.language.isoenen
dc.subjectLexicographicallyen
dc.subjectPlanar graphen
dc.subjectFour coloringen
dc.titlePlanar graph coloring is not self-reducible, assuming P ≠ NPen
dc.typeArticleen
Appears in Collections:Computer Science and Engineering

Files in This Item:

File Description SizeFormat
khullerpla91.pdf147.05 kBAdobe PDFView/Open
View Statistics

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - Feedback