Another Simple Algorithm for Edge-Coloring Bipartite Graphs
Summary :
A new edge-coloring algorithm for bipartite graphs is presented. This algorithm, based on the framework of the O(m log d + (m/d) log (m/d) log d) algorithm by Makino-Takabatake-Fujishige and the O(m log m) one by Alon, finds an optimal edge-coloring of a bipartite graph with m edges and maximum degree d in O(m log d + (m/d) log (m/d)) time. This algorithm does not require elaborate data structures, which the best known O(m log d) algorithm due to Cole-Ost-Schirra depends on.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E88-A No.5 pp.1303-1304
- Publication Date
- 2005/05/01
- Publicized
- Online ISSN
- DOI
- 10.1093/ietfec/e88-a.5.1303
- 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
Takashi TAKABATAKE, "Another Simple Algorithm for Edge-Coloring Bipartite Graphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E88-A, no. 5, pp. 1303-1304, May 2005, doi: 10.1093/ietfec/e88-a.5.1303.
Abstract: A new edge-coloring algorithm for bipartite graphs is presented. This algorithm, based on the framework of the O(m log d + (m/d) log (m/d) log d) algorithm by Makino-Takabatake-Fujishige and the O(m log m) one by Alon, finds an optimal edge-coloring of a bipartite graph with m edges and maximum degree d in O(m log d + (m/d) log (m/d)) time. This algorithm does not require elaborate data structures, which the best known O(m log d) algorithm due to Cole-Ost-Schirra depends on.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e88-a.5.1303/_p
Copy
@ARTICLE{e88-a_5_1303,
author={Takashi TAKABATAKE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Another Simple Algorithm for Edge-Coloring Bipartite Graphs},
year={2005},
volume={E88-A},
number={5},
pages={1303-1304},
abstract={A new edge-coloring algorithm for bipartite graphs is presented. This algorithm, based on the framework of the O(m log d + (m/d) log (m/d) log d) algorithm by Makino-Takabatake-Fujishige and the O(m log m) one by Alon, finds an optimal edge-coloring of a bipartite graph with m edges and maximum degree d in O(m log d + (m/d) log (m/d)) time. This algorithm does not require elaborate data structures, which the best known O(m log d) algorithm due to Cole-Ost-Schirra depends on.},
keywords={},
doi={10.1093/ietfec/e88-a.5.1303},
ISSN={},
month={May},}
Copy
TY - JOUR
TI - Another Simple Algorithm for Edge-Coloring Bipartite Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1303
EP - 1304
AU - Takashi TAKABATAKE
PY - 2005
DO - 10.1093/ietfec/e88-a.5.1303
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E88-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2005
AB - A new edge-coloring algorithm for bipartite graphs is presented. This algorithm, based on the framework of the O(m log d + (m/d) log (m/d) log d) algorithm by Makino-Takabatake-Fujishige and the O(m log m) one by Alon, finds an optimal edge-coloring of a bipartite graph with m edges and maximum degree d in O(m log d + (m/d) log (m/d)) time. This algorithm does not require elaborate data structures, which the best known O(m log d) algorithm due to Cole-Ost-Schirra depends on.
ER -
English
