- search hit 1 of 1
On-line rankings of graphs
Please always quote using this URN: urn:nbn:de:0297-zib-3011
- A (vertex) $k$-ranking of a graph $G=(V,E)$ is a mapping $ p:V\to \{1,\dots,k\}$ such that each path with endvertices of the same color $i$ contains an internal vertex of color $\ge i+1$. In the on-line coloring algorithms, the vertices $v_1,\dots,v_n$ arrive one by one in an unrestricted order, and only the edges inside the set $\{v_1,\dots,v_i\}$ are known when the color of $v_i$ has to be chosen. We characterize those graphs for which a 3-ranking can be found on-line. We also prove that the greedy (First-Fit) on-line algorithm, assigning the smallest feasible color to the next vertex at each step, generates a $(3\log_2 n)$-ranking for the path with $n \geq 2$ vertices, independently of the order in which the vertices are received.
Author: | Ingo Schiermeyer, Zsolt Tuza, Margit Voigt |
---|---|
Document Type: | ZIB-Report |
Date of first Publication: | 1997/07/10 |
Series (Serial Number): | ZIB-Report (SC-97-32) |
ZIB-Reportnumber: | SC-97-32 |
Published in: | Appeared in: Discrete Mathematics, 212 (2000), 141-147 |