Changes between Version 1 and Version 3 of Ticket #7662


Ignore:
Timestamp:
08/02/10 12:02:23 (12 years ago)
Author:
ncohen
Comment:

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #7662

    • Property Status changed from new to needs_review
    • Property Summary changed from Chordal Graphs to Update is_chordal to return certificates

  • Ticket #7662 – Description

    v1 v3  
    1 Create a module for chordal graphs :
     1This 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.
    22
    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*
     3Nathann