% file:         METR95-09
% author:       Yausko MATSUI and Tomomi MATSUI 
% organization: Math. Eng. #2 Lab. (Tomomi MATSUI)
% email:        tomomi@misojiro.t.u-tokyo.ac.jp
% title:        An Enumeration Algorithm for the Edge Coloring Problem
%               on Bipartite Graphs  
% keywords:     graph coloring, enumeration problem 
% language:     English


@techreport   {METR95-09,
    AUTHOR="Y. Matsui and T. Matsui",
    TITLE="An Enumeration Algorithm for the Edge Coloring Problem
           on Bipartite Graphs",
    YEAR=1995,
    INSTITUTION="University of Tokyo",
    TYPE="Research Report \mbox{METR} 95-09,
          Dept. of Mathematical Engineering and Information Physics,
          Faculty of Engineering"}

\begin{abstract}
In this paper, we propose an algorithm
 for finding all the edge colorings 
 in bipartite graphs.
Our algorithm requires 
 \ms{\Order (m\log \Delta + K \min \{n^2+m, m \log \Delta \})} time 
 and \ms{\Order (m\Delta)} space,
 where \ms{n} denotes the number of vertices,
  \ms{m} denotes the number of edges,
  \ms{\Delta} denotes the number of maximum degree,
  and \ms{K} denotes the number of edge colorings.
\end{abstract}