Opened 12 months ago
Closed 11 months ago
#30993 closed enhancement (fixed)
add pre processing for treewidth
Reported by:  dcoudert  Owned by:  

Priority:  major  Milestone:  sage9.3 
Component:  graph theory  Keywords:  
Cc:  Merged in:  
Authors:  David Coudert  Reviewers:  Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  64fa9bb (Commits, GitHub, GitLab)  Commit:  64fa9bb42ce8e4f49a88e50cfd0d0aa1a5836346 
Dependencies:  Stopgaps: 
Description
Use decomposition by clique minimal separators as a preprocessing for treewidth.
Change History (11)
comment:1 Changed 12 months ago by
 Branch set to public/graphs/30993_treewidth_and_atoms
 Commit set to 92c3e44bbaeab7fc5a37674079719034a67d1c17
 Dependencies changed from 30986 to #30986
 Status changed from new to needs_review
comment:2 Changed 12 months ago by
 Commit changed from 92c3e44bbaeab7fc5a37674079719034a67d1c17 to 2a9d49a8c1fa2661216a9819b797013f081ba875
Branch pushed to git repo; I updated commit sha1. New commits:
2a9d49a  trac #30993: minor improvement

comment:3 Changed 12 months ago by
 Commit changed from 2a9d49a8c1fa2661216a9819b797013f081ba875 to b53379e795cf0431f31769ae474780796399fc25
comment:4 Changed 12 months ago by
This last commit adds 2 methods, one to get the width of a treedecomposition, and the other to merge the treedecompositions of the atoms of the input graph to get a treedecomposition for the graph. This last method will be reused for the computation of treelength.
In addition, we add parameter kmin
to search for a treedecomposition of width at least kmin
. This is useful to speed up computations when processing many atoms.
comment:5 Changed 12 months ago by
 Dependencies #30986 deleted
I'm removing the dependency to #30986 as it has been merge in sage 9.3.beta3.
comment:6 Changed 12 months ago by
 Commit changed from b53379e795cf0431f31769ae474780796399fc25 to 36b31b90cfa471ade415a6f2634274bfb071f54b
Branch pushed to git repo; I updated commit sha1. New commits:
36b31b9  trac #30993: avoid extra validity test

comment:7 Changed 12 months ago by
 Commit changed from 36b31b90cfa471ade415a6f2634274bfb071f54b to 64fa9bb42ce8e4f49a88e50cfd0d0aa1a5836346
Branch pushed to git repo; I updated commit sha1. New commits:
64fa9bb  trac #30993: ensure consistence of parameter algorithm

comment:8 Changed 12 months ago by
When tdlib
is installed, the recursive calls were mixing the usage of 'sage'
and 'tdlib'
. This is now much more consistent.
comment:9 Changed 12 months ago by
 Reviewers set to Frédéric Chapoton
 Status changed from needs_review to positive_review
ok, looks good (superficiellement)
comment:10 Changed 12 months ago by
Thank you !
comment:11 Changed 11 months ago by
 Branch changed from public/graphs/30993_treewidth_and_atoms to 64fa9bb42ce8e4f49a88e50cfd0d0aa1a5836346
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
move method treewidth to new module tree_Decomposition.pyx
add method to check if a tree decomposition is valid
add method to reduce a tree decomposition
trac #30993: use atoms_and_clique_separators in treewidth