The search functionality is under construction.

The search functionality is under construction.

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.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.5 pp.1062-1065

- Publication Date
- 2002/05/01

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)

- Category

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Masakuni TAKI, Mikihito SUGIURA, Toshinobu KASHIWABARA, "On-Line Edge-Coloring Algorithms for Degree-Bounded Bipartite Graphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E85-A, no. 5, pp. 1062-1065, May 2002, doi: .

Abstract: 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.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e85-a_5_1062/_p

Copy

@ARTICLE{e85-a_5_1062,

author={Masakuni TAKI, Mikihito SUGIURA, Toshinobu KASHIWABARA, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={On-Line Edge-Coloring Algorithms for Degree-Bounded Bipartite Graphs},

year={2002},

volume={E85-A},

number={5},

pages={1062-1065},

abstract={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.},

keywords={},

doi={},

ISSN={},

month={May},}

Copy

TY - JOUR

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

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 1062

EP - 1065

AU - Masakuni TAKI

AU - Mikihito SUGIURA

AU - Toshinobu KASHIWABARA

PY - 2002

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E85-A

IS - 5

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - May 2002

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

ER -