Publikation: The Interval Constrained 3-Coloring Problem
Lade...
Dateien
Datum
2010
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
DOI (zitierfähiger Link)
ArXiv-ID
Internationale Patentnummer
Link zur Lizenz
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
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.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
Konferenz
LATIN 2010 : Theoretical Informatics ; 9th Latin American Symposium, 19. Apr. 2010 - 23. Apr. 2010, Oaxaca, Mexico
Rezension
undefined / . - undefined, undefined
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_51BibTex
@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>Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
