On computing optimal linear diagrams

DOI10.1007/978-3-031-15146-0_2zbMath1524.68433arXiv2206.08631OpenAlexW4294837711MaRDI QIDQ6108740

Martin Nöllenburg, Alexander Dobler

Publication date: 26 July 2023

Published in: Diagrammatic Representation and Inference (Search for Journal in Brave)

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

zbMATH Keywords

TSPNP-hardnesslinear diagramsconsecutive onesalgorithm benchmarking

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
• Consecutive block minimization is 1.5-approximable
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Euclidean traveling salesman problem is NP-complete
• Hardness results on the gapped consecutive-ones property problem
• Heuristic methods to consecutive block minimization
• Iterated local search for consecutive block minimization
• The Travelling Salesman and the PQ-Tree
• On the Gapped Consecutive-Ones Property
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Polynomial Complete Consecutive Information Retrieval Problems
• A note on the NP-hardness of the consecutive block minimization problem

This page was built for publication: On computing optimal linear diagrams