On the path-width of integer linear programming

DOI10.1016/J.IC.2016.07.010MaRDI QIDQ515665zbMATH OpenOpenAlexFDO

Authors Constantin Enea, Peter Habermehl, Omar Inverso, Gennaro Parlato

Publication date 16 March 2017

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://eprints.soton.ac.uk/386737/1/final.pdf

zbMATH Keywords

integer linear programmingautomatabounded path-widthfirst-order logic on graphs

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Integer programming (90C10) Decidability of theories and sets of sentences (03B25)

Recommendations

• On the path-width of integer linear programming
• scientific article; zbMATH DE number 2010046
• On Integer Programming and the Branch-Width of the Constraint Matrix
• Complexity of linear relaxations in integer programming
• scientific article; zbMATH DE number 3847219
• A linear algorithm for integer programming in the plane
• On the integer max-linear programming problem
• scientific article; zbMATH DE number 3511865
• scientific article; zbMATH DE number 4209912
• Integer Linear Programs and Local Search for Max-Cut

Cites work

• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 1979550 (Why is no real title available?)
• A Temporal Logic for Multi-threaded Programs
• A perfect model for bounded verification
• A unifying approach for multistack pushdown automata
• Adding nesting structure to words
• An Automatic Method of Solving Discrete Programming Problems
• Context-Bounded Analysis of Concurrent Queue Systems
• Factoring polynomials with rational coefficients
• Linear-time model-checking for multithreaded programs under scope-bounding
• Model-checking of ordered multi-pushdown automata
• On Context-Free Languages
• On the complexity of integer programming
• On the path-width of integer linear programming
• Parametrized complexity theory.
• Reachability analysis of communicating pushdown systems
• Reachability of multistack pushdown systems with scope-bounded matching relations
• Scope-bounded multistack pushdown systems: fixed-point, sequentialization, and tree-width
• Scope-bounded pushdown languages
• Scope-bounded pushdown languages
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The structure of the models of decidable monadic theories of graphs
• The tree width of auxiliary storage
• Tools and Algorithms for the Construction and Analysis of Systems
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(5)

• The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints
• On the decidability of finding a positive ILP-instance in a regular set of ILP-instances
• On the path-width of integer linear programming
• On the decidability of finding a positive ILP-instance in a regular set of ILP-instances
• Using ILP/SAT to determine pathwidth, visibility representations, and other grid-based graph drawings

This page was built for publication: On the path-width of integer linear programming

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