Changes between Initial Version and Version 2 of Ticket #17893


Ignore:
Timestamp:
03/04/15 16:39:51 (6 years ago)
Author:
ncohen
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #17893

    • Property Status changed from new to needs_review
    • Property Commit changed from to 427e907433481b576b57769fc09949ac12e8765a
    • Property Branch changed from to u/ncohen/17893
  • Ticket #17893 – Description

    initial v2  
    11As reported on asksage [1], the function `Graph.treewidth` can return incorrect tree decompositions.
     2
     3{{{
     4sage: graphs.PathGraph(10).treewidth(certificate=True).vertices()
     5[{2}, {1}, {4}, {8, 9}, {8}, {6}, {0}, {3}, {5}, {7}]
     6}}}
    27
    38The computations are actually done right (the width returned is correct), but my attempts to "simplify" the tree while it is being built simplified.. a bit too much.
     
    510The way it is done now is a bit more correct, though a tad more ressource-consuming. Nothing important, as the post-processing is infiinitely cheaper than the actual solving anyway.
    611
     12{{{
     13sage: graphs.PathGraph(10).treewidth(certificate=True).vertices()
     14[{0, 1}, {4, 5}, {1, 2}, {2, 3}, {8, 7}, {8, 9}, {6, 7}, {5, 6}, {3, 4}]
     15}}}
     16
    717Nathann
    818