DocumentCode :
2363214
Title :
Algorithms for robust graph coloring on paths
Author :
Bracho, Rafael López ; Rodríguez, Javier Ramírez ; Martíne, Francisco Javier Zaragoza
Author_Institution :
Departamento de Sistemas, Univ. Autonoma Metropolitana Unidad Azcapotzalco, Mexico City, Mexico
fYear :
2005
fDate :
7-9 Sept. 2005
Firstpage :
9
Lastpage :
12
Abstract :
We study algorithms for the robust graph coloring problem on paths: Given a blue path and a red path (with costs on its edges) on the same set of vertices, find a 3-coloring of the blue path that minimizes the sum of the costs of the red edges whose ends have the same color. First we give an exact but exponential-time algorithm. Then we give a randomized algorithm and we prove that the expected cost of its output is bounded above by half the cost of the red edges and we prove that this bound is sharp. Later, we give a greedy algorithm and we prove that the cost of its output is also bounded above by half the cost of the red edges. Finally, we present some results regarding the maximization problem and we propose some conjectures.
Keywords :
computational complexity; graph colouring; greedy algorithms; randomised algorithms; exponential-time algorithm; greedy algorithm; maximization problem; randomized algorithm; robust graph coloring; Cities and towns; Costs; Greedy algorithms; Robustness; Telephony;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Electrical and Electronics Engineering, 2005 2nd International Conference on
Print_ISBN :
0-7803-9230-2
Type :
conf
DOI :
10.1109/ICEEE.2005.1529561
Filename :
1529561
Link To Document :
بازگشت