QUBO formulations of the longest path problem

DOI10.1016/J.TCS.2021.02.021MaRDI QIDQ2658047zbMATH OpenOpenAlexFDO

Authors Joey McCollum, Thomas P. Krauss

Publication date 18 March 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2021.02.021

zbMATH Keywords

graph theorylongest pathquadratic unconstrained binary optimizationQUBO

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• QUBO formulations for the graph isomorphism problem and related problems
• The bipartite QUBO
• Logical and inequality implications for reducing the size and difficulty of quadratic unconstrained binary optimization problems
• Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem
• Introduction to QUBO

Cites work

• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 3974318 (Why is no real title available?)
• scientific article; zbMATH DE number 1875406 (Why is no real title available?)
• scientific article; zbMATH DE number 866055 (Why is no real title available?)
• A linear-time algorithm for the longest path problem in rectangular grid graphs
• A new modeling and solution approach for the number partitioning problem
• Algorithms and Computation
• Color-coding
• Compact quadratizations for pseudo-Boolean functions
• Faster deterministic parameterized algorithm for \(k\)-path
• Introduction to algorithms.
• Longest path analysis in networks of queues: dynamic scheduling problems
• On approximating the longest path in a graph
• Pseudo-Boolean optimization
• Randomized divide-and-conquer: improved path, matching, and packing algorithms
• The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
• The quantum adiabatic optimization algorithm and local minima

Cited in

(1)

• QUBO formulations for the graph isomorphism problem and related problems

This page was built for publication: QUBO formulations of the longest path problem

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