Piotr Borowiecki ; Dariusz Dereniowski - On-line ranking of split graphs

dmtcs:603 - Discrete Mathematics & Theoretical Computer Science, August 22, 2013, Vol. 15 no. 2 - https://doi.org/10.46298/dmtcs.603
On-line ranking of split graphsArticle

Authors: Piotr Borowiecki ORCID1; Dariusz Dereniowski ORCID1

  • 1 Department of Algorithms and Systems Modelling [ETI GUT]

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.


Volume: Vol. 15 no. 2
Section: Graph and Algorithms
Published on: August 22, 2013
Accepted on: June 9, 2015
Submitted on: May 21, 2009
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Consultation statistics

This page has been seen 705 times.
This article's PDF has been downloaded 485 times.