Publikation:

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

Vorschaubild

Dateien

bl_cr3cg_06.pdf
bl_cr3cg_06.pdfGröße: 452.23 KBDownloads: 486

Datum

2006

Autor:innen

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

URI (zitierfähiger Link)
http://nbn-resolving.de/urn:nbn:de:bsz:352-opus-73392
DOI (zitierfähiger Link)
https://doi.org/10.1007/11821069_18
ArXiv-ID

Internationale Patentnummer

Link zur Lizenz
Attribution-NonCommercial-NoDerivs 2.0 Generic

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Open Access Green

Sammlungen

Informatik und Informationswissenschaft: Publikationen
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

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.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Konferenz

Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690BRANDES, 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>

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
Ja
Begutachtet
Diese Publikation teilen