Quantum solutions for densest \(k\)-subgraph problems

DOI10.1007/s41965-019-00030-1zbMath1469.68060OpenAlexW3004745191MaRDI QIDQ1983021

Michael J. Dinneen, Cristian S. Calude, Richard Hua

Publication date: 14 September 2021

Published in: Journal of Membrane Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s41965-019-00030-1

zbMATH Keywords

quantum annealinginteger programming problemsquadratic unconstrained binary optimizationdensest \(k\)-subgraph problemD-wave 2X

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Graph theory (including graph drawing) in computer science (68R10) Quantum algorithms and complexity in the theory of computing (68Q12)

Uses Software

• NetworkX
• SageMath
• MotifCut
• CIDANE

Cites Work

• Fast clique minor generation in Chimera qubit connectivity graphs
• Clustering and domination in perfect graphs
• Degree sequences of random graphs
• QUBO formulations for the graph isomorphism problem and related problems
• The Elimination form of the Inverse and its Application to Linear Programming
• On Finding Dense Subgraphs
• A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing
• Different Formulations for Solving the HeaviestK-Subgraph Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Quantum solutions for densest \(k\)-subgraph problems