Changes between Version 1 and Version 3 of Ticket #7662
- Timestamp:
- 08/02/10 12:02:23 (12 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
Ticket #7662
-
Property
Status
changed from
new
toneeds_review
-
Property
Summary
changed from
Chordal Graphs
toUpdate is_chordal to return certificates
-
Property
Status
changed from
-
Ticket #7662 – Description
v1 v3 1 Create a module for chordal graphs : 1 This patch lets is_chordal return a certificate when asked to do so. The former algorithm is kept, and several lines are added to collect the certificate on the way and return it. 2 2 3 * Perfect elimination order ( use #7541 ) 4 * Move is-chordal in this module 5 * Polynomial-time algorithms for 6 * Vertex coloring 7 * Max clique/stable 8 * MaxBFS 9 * BFS* 3 Nathann