Edge-coloring bipartite multigraphs in O(E log D) time

Richard Cole; Kirstin Ost; Stefan Schirra

doi:10.1007/s004930170002

Edge-coloring bipartite multigraphs in O(E log D) time

Richard Cole, Kirstin Ost, Stefan Schirra

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

Let V, E, and D denote the cardinality of the vertex set, the cardinality of the edge set, and the maximum degree of a bipartite multigraph G. We show that a minimal edge-coloring of G can be computed in O(E log D) time. This result follows from an algorithm for finding a matching in a regular bipartite graph in O(E) time.

Original language	English (US)
Pages (from-to)	5-12
Number of pages	8
Journal	Combinatorica
Volume	21
Issue number	1
DOIs	https://doi.org/10.1007/s004930170002
State	Published - 2001

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/s004930170002

Cite this

@article{eb185a00a3c44c40978c828806124e99,

title = "Edge-coloring bipartite multigraphs in O(E log D) time",

abstract = "Let V, E, and D denote the cardinality of the vertex set, the cardinality of the edge set, and the maximum degree of a bipartite multigraph G. We show that a minimal edge-coloring of G can be computed in O(E log D) time. This result follows from an algorithm for finding a matching in a regular bipartite graph in O(E) time.",

author = "Richard Cole and Kirstin Ost and Stefan Schirra",

note = "Funding Information: * Th is work was supported in part by NSF grant CCR-9800085.",

year = "2001",

doi = "10.1007/s004930170002",

language = "English (US)",

volume = "21",

pages = "5--12",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "1",

}

TY - JOUR

T1 - Edge-coloring bipartite multigraphs in O(E log D) time

AU - Cole, Richard

AU - Ost, Kirstin

AU - Schirra, Stefan

N1 - Funding Information: * Th is work was supported in part by NSF grant CCR-9800085.

PY - 2001

Y1 - 2001

N2 - Let V, E, and D denote the cardinality of the vertex set, the cardinality of the edge set, and the maximum degree of a bipartite multigraph G. We show that a minimal edge-coloring of G can be computed in O(E log D) time. This result follows from an algorithm for finding a matching in a regular bipartite graph in O(E) time.

AB - Let V, E, and D denote the cardinality of the vertex set, the cardinality of the edge set, and the maximum degree of a bipartite multigraph G. We show that a minimal edge-coloring of G can be computed in O(E log D) time. This result follows from an algorithm for finding a matching in a regular bipartite graph in O(E) time.

UR - http://www.scopus.com/inward/record.url?scp=0040438506&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0040438506&partnerID=8YFLogxK

U2 - 10.1007/s004930170002

DO - 10.1007/s004930170002

M3 - Article

AN - SCOPUS:0040438506

SN - 0209-9683

VL - 21

SP - 5

EP - 12

JO - Combinatorica

JF - Combinatorica

IS - 1

ER -

Edge-coloring bipartite multigraphs in O(E log D) time

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this