On-Line Edge-Coloring Algorithms for Degree-Bounded Bipartite Graphs

Masakuni TAKI
Mikihito SUGIURA

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E85-A    No.5    pp.1062-1065
Publication Date: 2002/05/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
on-line algorithm,  randomization,  edge-coloring,  

Full Text: PDF>>
Buy this Article

A kind of online edge-coloring problems on bipartite graphs is considered. The input is a graph (typically with no edges) and a sequence of operations (edge addition and edge deletion) under the restriction that at any time the graph is bipartite and degree-bounded by k, where k is a prescribed integer. At the time of edge addition, the added edge can be irrevocably assigned a color or be left uncolored. No other coloring or color alteration is allowed. The problem is to assign colors as many times as possible using k colors. Two algorithms are presented: one with competitiveness coefficient 1/4 against oblivious adversaries, and one with competitiveness coefficient between 1/4 and 1/2 with the cost of requiring more random bits than the former algorithm, also against oblivious adversaries.