[Boost-bugs] [Boost C++ Libraries] #8317: Edge coloring

Subject: [Boost-bugs] [Boost C++ Libraries] #8317: Edge coloring
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2013-03-20 17:23:40

#8317: Edge coloring
-----------------------------------+----------------------------------------
 Reporter:  uzytkownik2@…          |       Owner:  jewillco      
     Type:  Patches                |      Status:  new           
Milestone:  To Be Determined       |   Component:  graph         
  Version:  Boost 1.52.0           |    Severity:  Not Applicable
 Keywords:                         |  
-----------------------------------+----------------------------------------
 Currently there is no edge coloring algorithm in boost. While it is
 possible to color line graph it is suboptimal as:

  * It uses in worst case 2d-1 colors where d is maximum degree of graph
  * It requires additional bookkeeping (creation of line graph, storing
 edge numbering, etc).

 The attached patch allows to color in-place using at most d+1 colors.

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/8317>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.