Trichotomy for the reconfiguration problem of integer linear systems

DOI10.1007/978-3-030-39881-1_29zbMath1477.68125arXiv1911.02786OpenAlexW3115044416MaRDI QIDQ5896129

Kei Kimura, Akira Suzuki

Publication date: 22 July 2020

Published in: Theoretical Computer Science, WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1911.02786

zbMATH Keywords

reconfigurationcombinatorial reconfigurationcomplexity indexinteger linear systemsinteger linear systemcomplexity trichotomy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Trichotomy for the reconfiguration problem of integer linear systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding shortest paths between graph colourings
• The complexity of rerouting shortest paths
• On the complexity of reconfiguration problems
• Trichotomy for integer linear systems based on their sign patterns
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• Simplicial pivoting algorithms for a tractable class of integer programs
• Introduction to reconfiguration
• Feasibility checking in Horn constraint systems through a reduction based approach
• A combinatorial algorithm for Horn programs
• The complexity of change
• Integer Programming with a Fixed Number of Variables
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• On the complexity of integer programming
• A Complexity Index for Satisfiability Problems
• On deciding the non‐emptiness of 2SAT polytopes with respect to First Order Queries
• Frontiers of Combining Systems
• Trichotomy for the reconfiguration problem of integer linear systems
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• Efficient algorithms for integer programs with two variables per constraint.

This page was built for publication: Trichotomy for the reconfiguration problem of integer linear systems