episciences.org_603_1675654607
1675654607
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
13658050
08
22
2013
Vol. 15 no. 2
Graph and Algorithms
Online ranking of split graphs
Piotr
Borowiecki
https://orcid.org/0000000252396540
Dariusz
Dereniowski
https://orcid.org/0000000340004818
Graphs and Algorithms
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 online algorithms for vertex ranking of split graphs, we prove that the worst case ratio of the number of colors used by any online ranking algorithm and the number of colors used in an optimal offline solution may be arbitrarily large. This negative result motivates us to investigate semi online algorithms, where a split graph is presented online but its clique number is given in advance. We prove that there does not exist a (2ɛ)competitive semi online algorithm of this type. Finally, a 2competitive semi online algorithm is given.
08
22
2013
603
https://hal.science/hal00980767v1
10.46298/dmtcs.603
https://dmtcs.episciences.org/603

https://dmtcs.episciences.org/603/pdf

https://dmtcs.episciences.org/603/pdf