Dartmouth logo Dartmouth College Computer Science
Technical Report series
CS home
TR home
TR search TR listserv
By author: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
By number: 2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991, 1990, 1989, 1988, 1987, 1986

An Algorithm for Computing Edge Colorings on Regular Bipartite Multigraphs
Andrew S. Hannigan
Dartmouth TR2015-769

Abstract:

In this paper, we consider the problem of finding an edge coloring of a d-regular bipartite multigraph with 2n vertices and m=nd edges. The best known deterministic algorithm (by Cole, Ost, and Schirra) takes O(m log d) time to find an edge coloring of such a graph. This bound is achieved by combining an O(m)-time perfect-matching algorithm with the Euler partition algorithm. The O(m) time bound on the Cole, Ost, and Schirra perfect-matching algorithm has been shown to be optimal.

In this paper we present an alternative perfect-matching algorithm called QuickMatch. Empirical analysis shows that QuickMatch finds a perfect matching in O(m) time in the average case. The QuickMatch algorithm allows us to compute an edge coloring in O(m log d) in the average case. Due to its simplicity, the presented method is easy to implement and the constants in the time bound are small. Because of these features, QuickMatch is a highly practical and competitive method for finding edge colorings of d-regular bipartite multigraphs.

Note:

Senior Honors Thesis Advisor: Thomas H. Cormen


PDF PDF (668KB)

Bibliographic citation for this report: [plain text] [BIB] [BibTeX] [Refer]

Or copy and paste:
   Andrew S. Hannigan, "An Algorithm for Computing Edge Colorings on Regular Bipartite Multigraphs." Dartmouth Computer Science Technical Report TR2015-769, May 2013.


Notify me about new tech reports.

Search the technical reports.

To receive paper copy of a report, by mail, send your address and the TR number to reports AT cs.dartmouth.edu


Copyright notice: The documents contained in this server are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Technical reports collection maintained by David Kotz.