On-line edge-coloring algorithms for degree-bounded bipartite graphs

作     者：Taki, M Sugiura, M Kashiwabara, T 

作者机构：Nara Natl Coll Technol Dept Informat Engn Yamato Koriyama 6391080 Japan Matsushita Tsuushin Co Yokohama Kanagawa 2238639 Japan Osaka Univ Dept Informat & Math Sci Toyonaka Osaka 5608531 Japan 

出 版 物：《IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES》 (IEICE Trans Fund Electron Commun Comput Sci)

年 卷 期：2002年第E85A卷第5期

页      面：1062-1065页

核心收录：

学科分类：0808[工学-电气工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：on-line algorithm randomization edge-coloring 

摘      要：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.