Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Wrong results in Graph.treewidth() #19358

Closed
nathanncohen mannequin opened this issue Oct 5, 2015 · 7 comments
Closed

Wrong results in Graph.treewidth() #19358

nathanncohen mannequin opened this issue Oct 5, 2015 · 7 comments
Labels
c: graph theory p: major / 3 t: bug
Milestone
sage-6.10

Comments

@nathanncohen
Copy link
Mannequin

nathanncohen mannequin commented Oct 5, 2015

As reported in [#19249 comment:6] 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.

CC: @sagetrac-llarisch @dcoudert

Component: graph theory

Author: Nathann Cohen

Branch/Commit: 7667bf2

Reviewer: David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/19358
@nathanncohen nathanncohen mannequin added this to the sage-6.9 milestone Oct 5, 2015
@nathanncohen
Copy link
Mannequin Author

nathanncohen mannequin commented Oct 5, 2015

Branch: u/ncohen/19358

@nathanncohen nathanncohen mannequin added the s: needs review label Oct 5, 2015
@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Oct 5, 2015

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

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

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Oct 5, 2015

Commit: 7667bf2

@dcoudert
Copy link
Contributor

comment:3

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 ;)

@dcoudert
Copy link
Contributor

Reviewer: David Coudert

@dcoudert dcoudert modified the milestones: sage-6.9, sage-6.10 Oct 28, 2015
@nathanncohen
Copy link
Mannequin Author

nathanncohen mannequin commented Oct 28, 2015

comment:4

Thaaaaaaaaaaanks !

@vbraun
Copy link
Member

vbraun commented Oct 28, 2015

Changed branch from u/ncohen/19358 to 7667bf2

@vbraun vbraun closed this as completed in 9b2a96a Oct 28, 2015
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
c: graph theory p: major / 3 t: bug
Projects
None yet
Milestone
sage-6.10
Development

No branches or pull requests
2 participants
@vbraun @dcoudert