Coloring Random 3-Colorable Graphs with Non-uniform Edge Probabilities

Brandes, Ulrik; Lerner, Jürgen

Coloring Random 3-Colorable Graphs with Non-uniform Edge Probabilities

Dateien

bl_cr3cg_06.pdfGröße: 452.23 KBDownloads: 394

Datum

2006

Open Access-Veröffentlichung

Open Access Green

Sammlungen

Informatik und Informationswissenschaft

Publikationstyp

Beitrag zu einem Konferenzband

Publikationsstatus

Published

Erschienen in

KRÁLOVIČ, Rastislav, ed., Paweł URZYCZYN, ed.. Mathematical Foundations of Computer Science 2006. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 202-213. Lecture Notes in Computer Science. 4162. ISBN 978-3-540-37791-7. Available under: doi: 10.1007/11821069_18

Zusammenfassung

Random 3-colorable graphs that are generated according to a G(n, p)-like model can be colored optimally, if p ≥ c/n for some large constant c. However, these methods fail in a model where the edgeprobabilities are non-uniform and not bounded away from zero. We present a spectral algorithm that succeeds in such situations.

Fachgebiet (DDC)

004 Informatik

Zitieren

ISO 690

BRANDES, Ulrik, Jürgen LERNER, 2006. Coloring Random 3-Colorable Graphs with Non-uniform Edge Probabilities. In: KRÁLOVIČ, Rastislav, ed., Paweł URZYCZYN, ed.. Mathematical Foundations of Computer Science 2006. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 202-213. Lecture Notes in Computer Science. 4162. ISBN 978-3-540-37791-7. Available under: doi: 10.1007/11821069_18

BibTex

@inproceedings{Brandes2006Color-5918,
  year={2006},
  doi={10.1007/11821069_18},
  title={Coloring Random 3-Colorable Graphs with Non-uniform Edge Probabilities},
  number={4162},
  isbn={978-3-540-37791-7},
  publisher={Springer Berlin Heidelberg},
  address={Berlin, Heidelberg},
  series={Lecture Notes in Computer Science},
  booktitle={Mathematical Foundations of Computer Science 2006},
  pages={202--213},
  editor={Královič, Rastislav and Urzyczyn, Paweł},
  author={Brandes, Ulrik and Lerner, Jürgen}
}

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/5918">
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:01:22Z</dc:date>
    <dcterms:issued>2006</dcterms:issued>
    <dc:creator>Lerner, Jürgen</dc:creator>
    <dc:creator>Brandes, Ulrik</dc:creator>
    <dc:contributor>Lerner, Jürgen</dc:contributor>
    <dcterms:bibliographicCitation>First publ. in: Proceedings of the 31th International Symposium Mathematical Foundations of Computer Science (MFCS ´06) (LNCS 4162), 2006, pp. 202-213</dcterms:bibliographicCitation>
    <dc:language>eng</dc:language>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5918/1/bl_cr3cg_06.pdf"/>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5918"/>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5918/1/bl_cr3cg_06.pdf"/>
    <dc:contributor>Brandes, Ulrik</dc:contributor>
    <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-nc-nd/2.0/"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:abstract xml:lang="eng">Random 3-colorable graphs that are generated according to a G(n, p)-like model can be colored optimally, if p ≥ c/n for some large constant c. However, these methods fail in a model where the edgeprobabilities are non-uniform and not bounded away from zero. We present a spectral algorithm that succeeds in such situations.</dcterms:abstract>
    <dc:rights>Attribution-NonCommercial-NoDerivs 2.0 Generic</dc:rights>
    <dcterms:title>Coloring Random 3-Colorable Graphs with Non-uniform Edge Probabilities</dcterms:title>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:01:22Z</dcterms:available>
    <dc:format>application/pdf</dc:format>
  </rdf:Description>
</rdf:RDF>

Universitätsbibliographie

Ja