On-line ranking of split graphs

Abstract : A vertex ranking of a graph G is an assignment of positive integers (colors) to the vertices of G such that each path connecting two vertices of the same color contains a vertex of a higher color. Our main goal is to find a vertex ranking using as few colors as possible. Considering on-line algorithms for vertex ranking of split graphs, we prove that the worst case ratio of the number of colors used by any on-line ranking algorithm and the number of colors used in an optimal off-line solution may be arbitrarily large. This negative result motivates us to investigate semi on-line algorithms, where a split graph is presented on-line but its clique number is given in advance. We prove that there does not exist a (2-ɛ)-competitive semi on-line algorithm of this type. Finally, a 2-competitive semi on-line algorithm is given.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 2 (2), pp.195--214
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00980767
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : vendredi 18 avril 2014 - 16:43:51
Dernière modification le : jeudi 7 septembre 2017 - 01:03:46
Document(s) archivé(s) le : lundi 10 avril 2017 - 15:25:41

Fichier

1316-8278-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00980767, version 1

Collections

Citation

Piotr Borowiecki, Dariusz Dereniowski. On-line ranking of split graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 2 (2), pp.195--214. 〈hal-00980767〉

Partager

Métriques

Consultations de la notice

697

Téléchargements de fichiers

377