2016-10-05 15:49:36 -0500 | received badge | ● Popular Question (source) |

2015-03-03 09:39:17 -0500 | answered a question | treewidth() Hello Nathan. Thanks for your reply. I do not have the specific example, but here is another one. M = Matrix([[0, 0, 1, 0, 1],[0, 0, 1, 0, 0],[1, 1, 0, 1, 0],[0, 0, 1, 0, 0],[1, 0, 0, 0, 0]]) g = Graph(M) T = g.treewidth(certificate=True) T.vertices() The comand T.vertices() returns Clearly (0,2) is an edge of the original graph but the answer above does not have a bag that contains both 0 and 2. |

2015-03-02 19:41:25 -0500 | asked a question | treewidth() Is there a bug with the treewidth function? I let G be a tree on 5 nodes and calculate a tree decomposition. However, the answer I get does not seem to be correct as the set of vertices returned are {0},{1},{2,3},{3},{3,4}. The definition of a tree decomposition requires that if (i,j) is an edge in G then there is a bag that contains both i and j. But clearly the above tree decomposition does not have satisfy this property? To illustrate with a concrete example (not the one above): This returns: Clearly (0,2) is an edge of the original graph but the answer above does not have a bag that contains both 0 and 2. |

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.