On-Line Edge-Coloring Algorithms for Degree-Bounded Bipartite Graphs(Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• 社団法人電子情報通信学会の論文
• 2002-05-01

著者

• Kashiwabara Toshinobu

  The Author Is With The Department Of Informatics And Mathmatical Science Osaka University

• Sugiura Mikihito

  The Author Is With Matsushita Tsuushin Co.

• Taki Masakuni

  The Author Is With The Department Of Information Engineering Nara National College Of Technology

関連論文

• On-Line Edge-Coloring Algorithms for Degree-Bounded Bipartite Graphs(Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク