For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On-Line Edge-Coloring Algorithms for Degree-Bounded Bipartite Graphs
Masakuni TAKI Mikihito SUGIURA Toshinobu KASHIWABARA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2002/05/01
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>>
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.