Edge-Coloring Bipartite Multigraphs in $0(E\log D)$ Time
作者： Richard Cole , Kirstin Ost , Stefan Schirra
关键词:
摘要: Let $V$, $E$, and $D$ denote the cardinality of vertex set, edge maximum degree a bipartite multigraph $G$. We show that minimal edge-coloring $G$ can be computed in $O(E\log D)$ time.
springer.com
core.ac.uk
mpg.de
sci-hub.se 参考文章(9)
Richard John Cole, Two problems in graph theory Cornell University. ,(1982)
Shin-ichi Nakano, Xiao Zhou, Takao Nishizeki, Edge-coloring algorithms Computer Science Today. pp. 172- 183 ,(1995) , 10.1007/BFB0015243
Harold N Gabow, Oded Kariv, None, Algorithms for edge coloring bipartite graphs symposium on the theory of computing. pp. 184- 192 ,(1978) , 10.1145/800133.804346
Harold N. Gabow, Using euler partitions to edge color bipartite multigraphs International Journal of Parallel Programming. ,vol. 5, pp. 345- 355 ,(1976) , 10.1007/BF00998632
Ajai Kapoor, Romeo Rizzi, Edge-Coloring Bipartite Graphs Journal of Algorithms. ,vol. 34, pp. 390- 396 ,(2000) , 10.1006/JAGM.1999.1058
Gavriela Freund Lev, Nicholas Pippenger, Leslie G. Valiant, A fast parallel algorithm for routing in permutation networks IEEE Transactions on Computers. ,vol. 30, pp. 93- 100 ,(1981) , 10.1109/TC.1981.6312171
Ian Holyer, The NP-Completeness of Edge-Coloring SIAM Journal on Computing. ,vol. 10, pp. 718- 720 ,(1981) , 10.1137/0210055
John E. Hopcroft, Richard M. Karp, An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs SIAM Journal on Computing. ,vol. 2, pp. 225- 231 ,(1973) , 10.1137/0202019
Richard Cole, John Hopcroft, On Edge Coloring Bipartite Graphs SIAM Journal on Computing. ,vol. 11, pp. 540- 546 ,(1982) , 10.1137/0211043