10.46298/dmtcs.603
https://dmtcs.episciences.org/603
Borowiecki, Piotr
Piotr
Borowiecki
0000-0002-5239-6540
Dereniowski, Dariusz
Dariusz
Dereniowski
0000-0003-4000-4818
On-line ranking of split graphs
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 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.
episciences.org
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
2015-06-09
2013-08-22
2013-08-22
en
journal article
https://hal.science/hal-00980767v1
1365-8050
https://dmtcs.episciences.org/603/pdf
VoR
application/pdf
Discrete Mathematics & Theoretical Computer Science
Vol. 15 no. 2
Graph and Algorithms
Researchers
Students