Opened 4 years ago

Closed 4 years ago

#19358 closed defect (fixed)

Wrong results in Graph.treewidth()

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.10
Component: graph theory Keywords:
Cc: llarisch, dcoudert Merged in:
Authors: Nathann Cohen Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: 7667bf2 (Commits) Commit: 7667bf2e63c14bf2f4f8437a02f786dfbc507970
Dependencies: Stopgaps:

Description

As reported in 6:ticket:19249 the function Graph.treewidth makes an incorrect assumption by extending the current 'cut' with vertices adjacent to it only.

It is fixed by this branch.

Change History (5)

comment:1 Changed 4 years ago by ncohen

  • Branch set to u/ncohen/19358
  • Status changed from new to needs_review

comment:2 Changed 4 years ago by git

  • Commit set to 7667bf2e63c14bf2f4f8437a02f786dfbc507970

Branch pushed to git repo; I updated commit sha1. New commits:

7667bf2trac #19358: Wrong results in Graph.treewidth()

comment:3 Changed 4 years ago by dcoudert

  • Milestone changed from sage-6.9 to sage-6.10
  • Reviewers set to David Coudert
  • Status changed from needs_review to positive_review

Simple patch that does the job. For me the patch is good to go.

Let's hope we will have other methods to compute treewidth soon ;)

comment:4 Changed 4 years ago by ncohen

Thaaaaaaaaaaanks !

comment:5 Changed 4 years ago by vbraun

  • Branch changed from u/ncohen/19358 to 7667bf2e63c14bf2f4f8437a02f786dfbc507970
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.