Linearizable special cases of the quadratic shortest path problem

DOI10.1007/978-3-030-86838-3_19OpenAlexW3200034092MaRDI QIDQ2672440

Stefan Lendl, Bettina Klinz, Lasse Wulf, James B. Orlin, Gerhard J. Woeginger, Eranda Çela

Publication date: 8 June 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-86838-3_19

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

A linear time algorithm for linearizing quadratic and higher-order shortest path problems

Cites Work

• Linearizable special cases of the QAP
• Two classes of quadratic assignment problems that are solvable as linear assignment problems
• A branch-and-cut algorithm for quadratic assignment problems based on linearizations
• The directed subgraph homeomorphism problem
• A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
• A characterization of linearizable instances of the quadratic minimum spanning tree problem
• Special cases of the quadratic shortest path problem
• The quadratic shortest path problem: complexity, approximability, and solution methods
• The linearization problem of a binary quadratic problem and its applications
• The quadratic cycle cover problem: special cases and efficient bounds
• An O(n⁴) Algorithm for the QAP Linearization Problem
• A contribution to quadratic assignment problems
• On Solving the Quadratic Shortest Path Problem
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees