On the path-width of integer linear programming

DOI10.1016/j.ic.2016.07.010zbMath1362.68230OpenAlexW2089047607MaRDI QIDQ515665

Gennaro Parlato, Peter Habermehl, Constantin Enea, Omar Inverso

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

automatainteger linear programmingbounded path-widthfirst-order logic on graphs

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The structure of the models of decidable monadic theories of graphs
• Factoring polynomials with rational coefficients
• Parametrized complexity theory.
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Model-Checking of Ordered Multi-Pushdown Automata
• A Temporal Logic for Multi-threaded Programs
• A Unifying Approach for Multistack Pushdown Automata
• Scope-bounded multistack pushdown systems: fixed-point, sequentialization, and tree-width
• A Perfect Model for Bounded Verification
• Reachability of Multistack Pushdown Systems with Scope-Bounded Matching Relations
• An Automatic Method of Solving Discrete Programming Problems
• Weak Second‐Order Arithmetic and Finite Automata
• Adding nesting structure to words
• On the complexity of integer programming
• Linear-Time Model-Checking for Multithreaded Programs under Scope-Bounding
• The tree width of auxiliary storage
• Context-Bounded Analysis of Concurrent Queue Systems
• On Context-Free Languages
• Tools and Algorithms for the Construction and Analysis of Systems
• Scope-Bounded Pushdown Languages
• Scope-Bounded Pushdown Languages
• Reachability Analysis of Communicating Pushdown Systems