IEICE TRANSACTIONS on Fundamentals
On-Line Edge-Coloring Algorithms for Degree-Bounded Bipartite Graphs
Summary :
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
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
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 -
English
