Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Minimum Coloring k-Colorable Graphs in Polynomial Average Time

Subramanian, C. R. (1999). Minimum Coloring k-Colorable Graphs in Polynomial Average Time. Journal of Algorithms, 33, 112-123.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-35DD-D Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-35DE-B
Genre: Zeitschriftenartikel

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Subramanian, C. R.1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: We present algorithms for minimum coloring k-colorable graphs drawn from random and semi-random models. In the first model, each allowed edge is included with indpendent probability p. In the second model, an adversary is given the power to vary the edge probability as the random instance is built. Semi-random models were introduced as a way of striking a balance between random graphs and worst-case adversaries. Our algorithms run in polynomial time on the average. Minimum coloring is harder than k-coloring because even a ''short certificate'' is not presently known for the optimality of a coloring.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2010-03-021999
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 518059
Anderer: Local-ID: C1256428004B93B8-B680BC80F5D56F99C12568AC005390EF-crsjalg
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Journal of Algorithms
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 33 Artikelnummer: - Start- / Endseite: 112 - 123 Identifikator: -