An ILP-based Proof System for the Crossing Number Problem

DOI10.4230/LIPICS.ESA.2016.29MaRDI QIDQ4606298zbMATH OpenOpenAlexFDO

Authors Markus Chimani, Tilo Wiedera

Publication date 2 March 2018

Full work available at URL https://doi.org/10.4230/LIPIcs.ESA.2016.29

zbMATH Keywords

integer linear programmingcrossing numberautomatic formal proof

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Integer programming (90C10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• scientific article; zbMATH DE number 4131955
• A branch-and-cut approach to the crossing number problem
• Algorithms for the fixed linear crossing number problem
• Crossing Numbers and Parameterized Complexity
• Crossing Number is NP-Complete
• An algorithm for the graph crossing number problem
• Some provably hard crossing number problems
• Integer programs for logic constraint satisfaction
• Numerical reasoning with an ILP system capable of lazy evaluation and customised search
• scientific article; zbMATH DE number 1487879

Cited in

(21)

• A survey of graphs with known or bounded crossing numbers
• The crossing numbers of join products of four graphs of order five with paths and cycles
• On the crossing numbers of Cartesian products of small graphs with paths, cycles and stars
• Characterizing all graphs with 2-exceptional edges
• The longest processing time rule for identical parallel machines revisited
• On 13-crossing-critical graphs with arbitrarily large degrees
• The crossing numbers of join product of four graphs on six vertices with discrete graphs
• On the crossing number of the join of the wheel on five vertices with the discrete graph
• Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics
• A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem
• An improved algorithm for a two-stage production scheduling problem with an outsourcing option
• Star-struck by fixed embeddings: modern crossing number heuristics
• There are no cubic graphs on 26 vertices with crossing number 10 or 11
• Approximating the 3-period incremental knapsack problem
• On the crossing number of the Cartesian product of a sunlet graph and a star graph
• The influence of separating cycles in drawings of \(K_5 \setminus e\) in the join product with paths and cycles
• On approximating the incremental knapsack problem
• Facets in the crossing number polytope
• Bounded degree conjecture holds precisely for \(c\)-crossing-critical graphs with \(c \le 12\)
• scientific article; zbMATH DE number 7559214 (Why is no real title available?)
• On the crossing numbers of Cartesian products of wheels and trees

Describes a project that uses

Uses Software

• ABACUS

This page was built for publication: An ILP-based Proof System for the Crossing Number Problem

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