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
- Branch set to u/ncohen/19358
- Status changed from new to needs_review
comment:2 Changed 4 years ago by
- Commit set to 7667bf2e63c14bf2f4f8437a02f786dfbc507970
comment:3 Changed 4 years ago by
- 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
Thaaaaaaaaaaanks !
comment:5 Changed 4 years ago by
- 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.
Branch pushed to git repo; I updated commit sha1. New commits:
trac #19358: Wrong results in Graph.treewidth()