descriptionPublicationkeyboard_double_arrow_right Article 01 Feb 2000 English Publisher:Elsevier BVJournal:Journal of Algorithms, volume 34, pages 390-396 (issn: 0196-6774,

Authors: A. Kapoor; Rizzi, Romeo;

doi: 10.1006/jagm.1999.1058

handle: 11572/28869

Edge-Coloring Bipartite Graphs

- Summary
- Subjects
- Metrics

Abstract

This note provides an algorithm for finding \(\Delta\)(colors)-edge-coloring of a bipartite graph of order \(n\) and size \(m\) in time \(T+O(m\log \Delta)\) where \(T\) is the time needed to find a perfect matching in a \(k\)-regular bipartite graph, \(k\leq \Delta\), and \(\Delta\) is the maximum degree of vertices. It is applied for finding a (\(\Delta +2\))-edge-coloring of a bipartite graph in time \(O(m\log \Delta)\).

Related Organizations

University of Padua
Italy
University of Trento
Italy

Keywords

algorithm, Graph theory (including graph drawing) in computer science, bipartite graph, perfect matching, edge-coloring

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	16
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%