Quantum algorithms for one-sided crossing minimization

DOI10.4230/LIPICS.GD.2024.20MaRDI QIDQ6920462zbMATH OpenFDO

Authors Susanna Caroppo, Giordano Da Lozzo, Giuseppe Di Battista

Publication date 7 October 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.GD.2024.20

zbMATH Keywords

exact exponential algorithmsone-sided crossing minimizationquantum divide and conquerquantum dynamic programmingquantum graph drawing

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Graph theory (including graph drawing) in computer science (68R10) Quantum computation (81P68) Multi-objective and goal programming (90C29)

Cites work

• A branch and bound algorithm for minimizing the number of crossing arcs in bipartite graphs
• A efficient fixed parameter tractable algorithm for 1-sided crossing minimzation
• A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization
• Edge crossings in drawings of bipartite graphs
• Encyclopedia of algorithms. In 3 volumes
• Exponential-time quantum algorithms for graph coloring problems
• Fast FAST
• Fixed parameter algorithms for one-sided crossing minimization revisited
• Graph Drawing
• scientific article; zbMATH DE number 2084271 (Why is no real title available?)
• scientific article; zbMATH DE number 5485441 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 1303024 (Why is no real title available?)
• scientific article; zbMATH DE number 1974113 (Why is no real title available?)
• Open problems around exact algorithms
• Quantum algorithms for one-sided crossing minimization
• Quantum graph drawing (best student paper)
• Quantum random access memory
• Quantum speedups for exponential-time dynamic programming algorithms
• Ranking and drawing in subexponential time

Cited in

(3)

• Quantum algorithms for one-sided crossing minimization
• Quantum algorithms for one-sided crossing minimization
• Quantum speedups for polynomial-time dynamic programming algorithms

This page was built for publication: Quantum algorithms for one-sided crossing minimization

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