Changes between Initial Version and Version 2 of Ticket #12716


Ignore:
Timestamp:
04/08/12 12:58:34 (8 years ago)
Author:
dcoudert
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #12716

    • Property Status changed from new to needs_review
    • Property Summary changed from Linear orderings of graphs to MILP formulation and test functions for vertex separation
  • Ticket #12716 – Description

    initial v2  
    1 This patch gathers (di)graph decompositions functions (path decompositions, vertex separation, etc.) when the decomposition is represented as linear ordering of the vertices. It also provides some measurement functions of linear orderings according to particular widths.
     1This patch implements a MILP formulation for the vertex separation and some test functions for evaluating the width of linear vertex orderings.
    22
    3 I propose to gather these functions inside an object of class `LinearOrdering` to ease access and prevent increasing the number of methods of (Di)Graphs objects.
    4 I'm ready to discuss / modify this patch.
    53
    6 I will later add other measurement functions (tree decomposition/treewidth, cutwidth,....) and some methods for computing optimal orderings according these width.
     4APPLY:
     5* [attachment:trac_12716_MILP.patch]