id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
11735 Bug in is_chordal ncohen tbd "As reported by Jan on sage-devel [1], the current implementation of is_chordal is incorrect. Given a vertex v adjacent to x and y (x and y being non-adjacent), a shortest path between x and y in G-v does not necessarily avoid the neighbors of v. Clearly.
Well, with this patch the shortest path is computed in the graph G with v and all its neighbors removed with the exception of x and y, so that it can not happen again.
Besides, as it is almost free to check that the certificate is indeed a hole, this patch adds a test just in case `:-)`
Nathann
Requires :
* #11738
Apply:
* [attachment:trac_11735.patch]
[1] https://groups.google.com/d/topic/sage-support/rU1VTz1Ou_I/discussion" defect closed major sage-4.8 graph theory fixed lsampaio ddestrada dcoudert sage-4.8.alpha4 Nathann Cohen David Coudert N/A