#30993 closed enhancement (fixed)

add pre processing for treewidth

Reported by: dcoudert Owned by:
Priority: major Milestone: sage-9.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:

Status badges

Description

Use decomposition by clique minimal separators as a pre-processing for treewidth.

Change History (11)

comment:1 Changed 12 months ago by dcoudert

  • 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

New commits:

ea8a5b2move method treewidth to new module tree_Decomposition.pyx
9a999feadd method to check if a tree decomposition is valid
3842a49add method to reduce a tree decomposition
92c3e44trac #30993: use atoms_and_clique_separators in treewidth

comment:2 Changed 12 months ago by git

  • Commit changed from 92c3e44bbaeab7fc5a37674079719034a67d1c17 to 2a9d49a8c1fa2661216a9819b797013f081ba875

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

2a9d49atrac #30993: minor improvement

comment:3 Changed 12 months ago by git

  • Commit changed from 2a9d49a8c1fa2661216a9819b797013f081ba875 to b53379e795cf0431f31769ae474780796399fc25

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

e0beb45trac #30993: merged with 9.3.beta3
b53379etrac #30993: further improvements

comment:4 Changed 12 months ago by dcoudert

This last commit adds 2 methods, one to get the width of a tree-decomposition, and the other to merge the tree-decompositions of the atoms of the input graph to get a tree-decomposition for the graph. This last method will be reused for the computation of treelength.

In addition, we add parameter kmin to search for a tree-decomposition of width at least kmin. This is useful to speed up computations when processing many atoms.

comment:5 Changed 12 months ago by dcoudert

  • 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 git

  • Commit changed from b53379e795cf0431f31769ae474780796399fc25 to 36b31b90cfa471ade415a6f2634274bfb071f54b

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

36b31b9trac #30993: avoid extra validity test

comment:7 Changed 12 months ago by git

  • Commit changed from 36b31b90cfa471ade415a6f2634274bfb071f54b to 64fa9bb42ce8e4f49a88e50cfd0d0aa1a5836346

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

64fa9bbtrac #30993: ensure consistence of parameter algorithm

comment:8 Changed 12 months ago by dcoudert

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 chapoton

  • 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 dcoudert

Thank you !

comment:11 Changed 11 months ago by vbraun

  • Branch changed from public/graphs/30993_treewidth_and_atoms to 64fa9bb42ce8e4f49a88e50cfd0d0aa1a5836346
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.