Ticket #8317 (closed Patches: fixed)
|Reported by:||uzytkownik2@…||Owned by:||jewillco|
|Milestone:||To Be Determined||Component:||graph|
|Version:||Boost 1.52.0||Severity:||Not Applicable|
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.
Changed 4 years ago by Maciej Piechotka <uzytkownik2@…>
- attachment 0001-Added-edge-coloring-algorithm.2.patch added