The Interval Constrained 3-Coloring Problem

Byrka, Jaroslaw; Karrenbauer, Andreas; Sanità, Laura

The Interval Constrained 3-Coloring Problem

Dateien

0907.3563v2.pdfGröße: 989.59 KBDownloads: 236

Datum

2010

Autor:innen

Byrka, Jaroslaw

Karrenbauer, Andreas

Sanità, Laura

Open Access-Veröffentlichung

Open Access Green

Sammlungen

Informatik und Informationswissenschaft
Zukunftskolleg

Publikationstyp

Beitrag zu einem Konferenzband

Publikationsstatus

Published

Erschienen in

LÓPEZ-ORTIZ, Alejandro, ed.. LATIN 2010 : Theoretical Informatics ; Proceedings. Berlin: Springer, 2010, pp. 591-602. Lecture Notes in Computer Science. 6034. ISSN 0302-9743. ISBN 978-3-642-12199-9. Available under: doi: 10.1007/978-3-642-12200-2_51

Zusammenfassung

In this paper, we settle the open complexity status of interval constrained coloring with a fixed number of colors. We prove that the problem is already NP-complete if the number of different colors is 3. Previously, it has only been known that it is NP-complete, if the number of colors is part of the input and that the problem is solvable in polynomial time, if the number of colors is at most 2. We also show that it is hard to satisfy almost all of the constraints for a feasible instance. This implies APX-hardness of maximizing the number of simultaneously satisfiable intervals.

Fachgebiet (DDC)

004 Informatik

Konferenz

LATIN 2010 : Theoretical Informatics ; 9th Latin American Symposium, 19. Apr. 2010 - 23. Apr. 2010, Oaxaca, Mexico

Zitieren

ISO 690

BYRKA, Jaroslaw, Andreas KARRENBAUER, Laura SANITÀ, 2010. The Interval Constrained 3-Coloring Problem. LATIN 2010 : Theoretical Informatics ; 9th Latin American Symposium. Oaxaca, Mexico, 19. Apr. 2010 - 23. Apr. 2010. In: LÓPEZ-ORTIZ, Alejandro, ed.. LATIN 2010 : Theoretical Informatics ; Proceedings. Berlin: Springer, 2010, pp. 591-602. Lecture Notes in Computer Science. 6034. ISSN 0302-9743. ISBN 978-3-642-12199-9. Available under: doi: 10.1007/978-3-642-12200-2_51

BibTex

@inproceedings{Byrka2010Inter-6232,
  year={2010},
  doi={10.1007/978-3-642-12200-2_51},
  title={The Interval Constrained 3-Coloring Problem},
  number={6034},
  isbn={978-3-642-12199-9},
  issn={0302-9743},
  publisher={Springer},
  address={Berlin},
  series={Lecture Notes in Computer Science},
  booktitle={LATIN 2010 : Theoretical Informatics ; Proceedings},
  pages={591--602},
  editor={López-Ortiz, Alejandro},
  author={Byrka, Jaroslaw and Karrenbauer, Andreas and Sanità, Laura}
}

RDF

<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/6232">
    <dcterms:issued>2010</dcterms:issued>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/6232"/>
    <dcterms:bibliographicCitation>First publ. in: arXiv:0907.3563v2 [cs.DM]</dcterms:bibliographicCitation>
    <dc:contributor>Byrka, Jaroslaw</dc:contributor>
    <dc:creator>Byrka, Jaroslaw</dc:creator>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6232/1/0907.3563v2.pdf"/>
    <dc:rights>terms-of-use</dc:rights>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/52"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6232/1/0907.3563v2.pdf"/>
    <dc:format>application/pdf</dc:format>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Karrenbauer, Andreas</dc:creator>
    <dcterms:abstract xml:lang="eng">In this paper, we settle the open complexity status of interval constrained coloring with a fixed number of colors. We prove that the problem is already NP-complete if the number of different colors is 3. Previously, it has only been known that it is NP-complete, if the number of colors is part of the input and that the problem is solvable in polynomial time, if the number of colors is at most 2. We also show that it is hard to satisfy almost all of the constraints for a feasible instance. This implies APX-hardness of maximizing the number of simultaneously satisfiable intervals.</dcterms:abstract>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:title>The Interval Constrained 3-Coloring Problem</dcterms:title>
    <dc:contributor>Karrenbauer, Andreas</dc:contributor>
    <dc:creator>Sanità, Laura</dc:creator>
    <dc:language>eng</dc:language>
    <dc:contributor>Sanità, Laura</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:10:24Z</dc:date>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:10:24Z</dcterms:available>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/52"/>
  </rdf:Description>
</rdf:RDF>

Universitätsbibliographie

Ja