# Using euler partitions to edge color bipartite multigraphs

@article{Gabow2005UsingEP, title={Using euler partitions to edge color bipartite multigraphs}, author={H. Gabow}, journal={International Journal of Computer \& Information Sciences}, year={2005}, volume={5}, pages={345-355} }

An algorithm for finding a minimal edge coloring of a bipartite multigraph is presented. The algorithm usesO(V1/2ElogV + V) time andO(E + V) space. It is based on a divide-and-conquer strategy, using euler partitions to divide the graph. A modification of the algorithm for matching is described. This algorithm finds a maximum matching of a regular bipartite graph with all degrees 2n, inO(E + V) time andO(E + V) space.

#### 54 Citations

Algorithms for Edge Coloring Bipartite Graphs and Multigraphs

- Mathematics, Computer Science
- SIAM J. Comput.
- 1982

Coloring algorithms that run in time $O(\min (m(\log n)^2 ,n^2 \log n))$ are presented and can be used to find maximum cardinality matchings on regular bipartite graphs in the above time bound. Expand

Another Simple Algorithm for Edge-Coloring Bipartite Graphs

- Mathematics, Computer Science
- IEICE Trans. Fundam. Electron. Commun. Comput. Sci.
- 2005

A new edge-coloring algorithm for bipartite graphs that does not require elaborate data structures, which the best known O(mlogd) algorithm due to Cole--Ost--Schirra depends on is presented. Expand

BIPARTITE EDGE COLORING IN O ( Am )

- 2005

We show that a minimum edge coloring of a bipartite graph can be found in O(Ll.m) time, where Ll. and m denote the maximum degree and the number of edges of G, respectively. It is equivalent to… Expand

Path multicoloring in spider graphs with even color multiplicity

- Computer Science, Mathematics
- Inf. Process. Lett.
- 2018

An exact polynomial-time algorithm for maximizing the number of colored paths with a given number of colors ( Max-PMC) in spider graphs with even admissible color multiplicity on each edge is obtained. Expand

Finding 1-Factors in Bipartite Regular Graphs and Edge-Coloring Bipartite Graphs

- Computer Science, Mathematics
- SIAM J. Discret. Math.
- 2002

A new and faster algorithm to find a 1-factor in a bipartite $\Delta$-regular graph with n nodes, m edges, and maximum degree $Delta$ is given. Expand

Matching, edge-colouring, dimers

- Mathematics, Computer Science
- 2003

Main results are improved complexity bounds for finding a perfect matching in a regular bipartite graph and for edge-colouring bipartites, the solution of a problem of Erdos and Renyi concerning lower bounds for the number of perfect matchings, and an improved lower bound for s dimer constant. Expand

Matching, Edge-Colouring, and Dimers

- Mathematics, Computer Science
- WG
- 2003

Improved complexity bounds for finding a perfect matching in a regular bipartite graph and for edge-colouring bipartITE graphs, the solution of a problem of Erdős and Renyi concerning lower bounds for the number of perfect matchings, and an improved lower bound for s dimer constant are surveyed. Expand

A simple algorithm for edge-coloring bipartite multigraphs

- Mathematics, Computer Science
- Inf. Process. Lett.
- 2003

A new, simpler algorithm for finding a proper k-edge-coloring of any bipartite multigraph G with n vertices and m edges is described, that runs in time O(m logm) as well. Expand

Minimum multiplicity edge coloring via orientation

- Computer Science, Mathematics
- Discret. Appl. Math.
- 2018

This paper investigates whether this approximation ratio can be improved by a more careful choice of the edge orientation in the first step, and shows how to produce an orientation which results in a solution with cost within a factor of 2 − 1 2 w of the optimal, thus yielding an approximation ratio strictly better than 2. Expand

Space-efficient Euler partition and bipartite edge coloring

- Mathematics, Computer Science
- Theor. Comput. Sci.
- 2019

A new data structure is presented here, the subgraph stack, that allows graph algorithms centered around recursive calls on substantially smaller subgraphs to be implemented in a space-efficient manner. Expand

#### References

SHOWING 1-7 OF 7 REFERENCES

An n5/2 Algorithm for Maximum Matchings in Bipartite Graphs

- Mathematics, Computer Science
- SIAM J. Comput.
- 1973

The present paper shows how to construct a maximum matching in a bipartite graph with n vertices and m edges in a number of computation steps proportional to $(m + n)\sqrt n $.

The Design and Analysis of Computer Algorithms

- Computer Science
- 1974

This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs. Expand

Using Euler Partitions to Edge Color Bipartite Multigraphs ; CU-CS-082-75 Computer Science Technical Reports. Paper 80

- Using Euler Partitions to Edge Color Bipartite Multigraphs ; CU-CS-082-75 Computer Science Technical Reports. Paper 80
- 1975

Two Algorithms for the TimeTable Problem

- Combinatorial Mathematics and Its Applications