Possible and Impossible Attempts to Solve the Treewidth Problem via ILPs

DOI10.1007/978-3-030-42071-0_7MaRDI QIDQ5042451zbMATH OpenOpenAlexFDO

Authors Alexander Grigoriev

Publication date 19 October 2022

Published in Treewidth, Kernels, and Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-42071-0_7

zbMATH Keywords

integer programmingpathwidthtreewidth

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• On the path-width of integer linear programming
• On the path-width of integer linear programming
• Linear ordering based MIP formulations for the vertex separation or pathwidth problem
• Linear ordering based MIP formulations for the vertex separation or pathwidth problem
• SOFSEM 2005: Theory and Practice of Computer Science

Cites work

• A branch-and-price-and-cut method for computing an optimal bramble
• A note on optimal area algorithms for upward drawings of binary trees
• Flow metrics
• Multimodal optimization by means of evolutionary algorithms
• New Approximation Techniques for Some Linear Ordering Problems
• Treewidth computations. I: Upper bounds
• Treewidth computations. II. Lower bounds

Cited in

(2)

• On integer linear programs for treewidth based on perfect elimination orderings
• On integer linear programs for treewidth based on perfect elimination orderings (extended version)

Describes a project that uses

Uses Software

• ComputeTW

This page was built for publication: Possible and Impossible Attempts to Solve the Treewidth Problem via ILPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5042451)