Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chimani, Markus, Ilsen, Max, Wiedera, Tilo
Format:	Preprint
Published:	2021
Subjects:	Discrete Mathematics Data Structures and Algorithms Combinatorics 68R10 (Primary) 05C10, 90C27 (Secondary) G.2.1; G.2.2; F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Directed Capacity-Preserving Subgraphs: Hardness and Exact Polynomial Algorithms
by: Chimani, Markus, et al.
Published: (2023)

Designing Capacitated Subnetworks for Shortest Path Routing
by: Chimani, Markus, et al.
Published: (2026)

Simple Approximations for General Spanner Problems
by: Bökler, Fritz, et al.
Published: (2025)

Exact Minimum Weight Spanners via Column Generation
by: Bökler, Fritz, et al.
Published: (2024)

Traffic-Oblivious Multi-Commodity Flow Network Design
by: Chimani, Markus, et al.
Published: (2025)

A Fast 3-Approximation for the Capacitated Tree Cover Problem with Edge Loads
by: Rockel-Wolff, Benjamin
Published: (2024)

On the Integrality Gap of Directed Steiner Tree LPs with Relatively Integral Solutions
by: Laekhanukit, Bundit
Published: (2024)

Polyhedral approach to weighted connected matchings in general graphs
by: Samer, Phillippe, et al.
Published: (2023)

Tighter Approximation for the Uniform Cost-Distance Steiner Tree Problem
by: Foos, Josefine, et al.
Published: (2023)

A Systematic Approach to Crossing Numbers of Cartesian Products with Paths
by: Asiri, Zayed, et al.
Published: (2024)

A near-complete resolution of the exponential-time complexity of k-opt for the traveling salesman problem
by: Heimann, Sophia, et al.
Published: (2025)

Optimized Degree Realization: Minimum Dominating Set & Maximum Matching
by: Bar-Noy, Amotz, et al.
Published: (2025)

Approximation algorithms for the prize-collecting rural postman problem
by: Li, Hong, et al.
Published: (2026)

No Traffic to Cry: Traffic-Oblivious Link Deactivation for Green Traffic Engineering
by: Ilsen, Max, et al.
Published: (2026)

Crossing Numbers of Beyond Planar Graphs Re-revisited: A Framework Approach
by: Chimani, Markus, et al.
Published: (2024)

The $k$-Opt algorithm for the Traveling Salesman Problem has exponential running time for $k \ge 5$
by: Heimann, Sophia, et al.
Published: (2024)

The Bottom-Left Algorithm for the Strip Packing Problem
by: Hougardy, Stefan, et al.
Published: (2024)

Loop unrolling of UCA models: distance labeling
by: Soulignac, Francisco J, et al.
Published: (2022)

On the thinness of trees
by: Bonomo-Braberman, Flavia, et al.
Published: (2025)

Temporalizing digraphs via linear-size balanced bi-trees
by: Bessy, Stéphane, et al.
Published: (2023)

Searching in trees with monotonic query times
by: Dereniowski, Dariusz, et al.
Published: (2024)

Graph burning: an overview of mathematical programs
by: Cajica-Maceda, Lourdes Beatriz, et al.
Published: (2025)

Computing distances is FPT on graph associahedra and W[2]-hard on hypergraphic polytopes
by: Cunha, Luís Felipe I., et al.
Published: (2025)

Revisiting Chazelle's Implementation of the Bottom-Left Heuristic: A Corrected and Rigorous Analysis
by: Michel, Stefan
Published: (2025)

Interval Graphs are Reconstructible
by: Heinrich, Irene, et al.
Published: (2025)

A note on the parameter $\ell$ in Buchbinder--Feldman's deterministic submodular matroid algorithm
by: Li, Shisheng
Published: (2026)

Pliability and Approximating Max-CSPs
by: Romero, Miguel, et al.
Published: (2019)

Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint
by: Buchbinder, Niv, et al.
Published: (2024)

Extending Exact Integrality Gap Computations for the Metric TSP
by: Cook, William, et al.
Published: (2026)

On the PLS-Completeness of $k$-Opt Local Search for the Traveling Salesman Problem
by: Heimann, Sophia, et al.
Published: (2026)

Low Recourse Arborescence Forests Under Uniformly Random Arcs
by: Dahlmeier, J Niklas, et al.
Published: (2025)

m-Eternal Domination and Variants on Some Classes of Finite and Infinite Graphs
by: Calamoneri, Tiziana, et al.
Published: (2025)

The Minimum Eternal Vertex Cover Problem on a Subclass of Series-Parallel Graphs
by: Calamoneri, Tiziana, et al.
Published: (2025)

Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs is Logarithmic
by: Loth, Jesse Campion, et al.
Published: (2022)

Killing a Vortex
by: Thilikos, Dimitrios M., et al.
Published: (2022)

Enumeration Kernels of Polynomial Size for Cuts of Bounded Degree
by: Komusiewicz, Christian, et al.
Published: (2023)

A counterexample to the conjecture on Biclique Partition number of Split Graphs and related problems
by: Babu, Anand, et al.
Published: (2026)

Cluster deletion and clique partitioning in graphs with bounded clique number
by: Galesi, Nicola, et al.
Published: (2025)

A Faster Algorithm for Independent Cut
by: Chernyshev, Vsevolod, et al.
Published: (2025)

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
by: Chen, Yijia, et al.
Published: (2023)