Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
  New approximation algorithms for the achromatic number

Krysta, P., & Lorys, K.(1998). New approximation algorithms for the achromatic number (MPI-I-1998-1-016). Saarbrücken: Max-Planck-Institut für Informatik.

Item is

Dateien

einblenden: Dateien
ausblenden: Dateien
:
MPI-I-98-1-016.pdf (beliebiger Volltext), 41MB
Name:
MPI-I-98-1-016.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Öffentlich
MIME-Typ / Prüfsumme:
application/pdf / [MD5]
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Krysta, Piotr1, Autor           
Lorys, Krzysztof2, Autor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: The achromatic number of a graph is the greatest number of colors in a coloring of the vertices of the graph such that adjacent vertices get distinct colors and for every pair of colors some vertex of the first color and some vertex of the second color are adjacent. The problem of computing this number is NP-complete for general graphs as proved by Yannakakis and Gavril 1980. The problem is also NP-complete for trees, that was proved by Cairnie and Edwards 1997. Chaudhary and Vishwanathan 1997 gave recently a $7$-approximation algorithm for this problem on trees, and an $O(\sqrt{n})$-approximation algorithm for the problem on graphs with girth (length of the shortest cycle) at least six. We present the first $2$-approximation algorithm for the problem on trees. This is a new algorithm based on different ideas than one by Chaudhary and Vishwanathan 1997. We then give a $1.15$-approximation algorithm for the problem on binary trees and a $1.58$-approximation for the problem on trees of constant degree. We show that the algorithms for constant degree trees can be implemented in linear time. We also present the first $O(n^{3/8})$-approximation algorithm for the problem on graphs with girth at least six. Our algorithms are based on an interesting tree partitioning technique. Moreover, we improve the lower bound of Farber {\em et al.} 1986 for the achromatic number of trees with degree bounded by three.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 1998
 Publikationsstatus: Erschienen
 Seiten: 26 p.
 Ort, Verlag, Ausgabe: Saarbrücken : Max-Planck-Institut für Informatik
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: Reportnr.: MPI-I-1998-1-016
BibTex Citekey: KrystaLorys98-1-016
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Research Report / Max-Planck-Institut für Informatik
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: - Identifikator: -