The interval constrained 3-coloring problem

Lade...
Vorschaubild
Dateien
Zu diesem Dokument gibt es keine Dateien.
Datum
2015
Autor:innen
Byrka, Jaroslaw
Sanità, Laura
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
ArXiv-ID
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Zeitschriftenartikel
Publikationsstatus
Published
Erschienen in
Theoretical Computer Science. 2015, 593, pp. 42-50. ISSN 0304-3975. eISSN 1879-2294. Available under: doi: 10.1016/j.tcs.2015.04.037
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 (even in the restricted case where each interval is used at most once). This implies APX-hardness of maximizing the number of simultaneously satisfiable intervals.

Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690BYRKA, Jaroslaw, Andreas KARRENBAUER, Laura SANITÀ, 2015. The interval constrained 3-coloring problem. In: Theoretical Computer Science. 2015, 593, pp. 42-50. ISSN 0304-3975. eISSN 1879-2294. Available under: doi: 10.1016/j.tcs.2015.04.037
BibTex
@article{Byrka2015-08inter-32969,
  year={2015},
  doi={10.1016/j.tcs.2015.04.037},
  title={The interval constrained 3-coloring problem},
  volume={593},
  issn={0304-3975},
  journal={Theoretical Computer Science},
  pages={42--50},
  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/32969">
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2016-02-15T13:05:03Z</dc:date>
    <dc:contributor>Byrka, Jaroslaw</dc:contributor>
    <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 (even in the restricted case where each interval is used at most once). This implies APX-hardness of maximizing the number of simultaneously satisfiable intervals.</dcterms:abstract>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/32969"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2016-02-15T13:05:03Z</dcterms:available>
    <dcterms:title>The interval constrained 3-coloring problem</dcterms:title>
    <dc:contributor>Sanità, Laura</dc:contributor>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:issued>2015-08</dcterms:issued>
    <dc:creator>Sanità, Laura</dc:creator>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Karrenbauer, Andreas</dc:creator>
    <dc:creator>Byrka, Jaroslaw</dc:creator>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:language>eng</dc:language>
    <dc:contributor>Karrenbauer, Andreas</dc:contributor>
  </rdf:Description>
</rdf:RDF>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
URL der Originalveröffentl.
Prüfdatum der URL
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Nein
Begutachtet
Diese Publikation teilen