A branch-and-cut approach to the crossing number problem
type: Item
instance of: scholarly article
title: A branch-and-cut approach to the crossing number problem
zbMATH Open document ID: 1146.05017
author: Christoph Buchheim
author: Markus Chimani
author: Dietmar Ebner
author: Carsten Gutwenger
author: Michael Jünger
author: Gunnar W. Klau
author: Petra Mutzel
author: René Weiskircher
published in: Discrete Optimization
publication date: 2008-10-29T00:00:00Z
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C57
zbMATH DE Number: 5358797
zbMATH Keywords: crossing number
zbMATH Keywords: branch-and-cut
zbMATH Keywords: column generation
describes a project that uses: ABACUS
describes a project that uses: PIGALE
describes a project that uses: OGDF
MaRDI profile type: Publication
full work available at URL: j.disopt.2007.05.006
OpenAlex ID: W2101447138
Wikidata QID: Q56977220
cites work: A framework for solving VLSI graph layout problems
cites work: Fundamentals of Computation Theory
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
cites work: An $O(m\log n)$-Time Algorithm for the Maximal Planar Subgraph Problem
cites work: A Better Approximation Algorithm for Finding Planar Subgraphs
cites work: Integer Programming and Combinatorial Optimization
cites work: Decomposition Principle for Linear Programs
cites work: On Cotree-Critical and DFS Cotree-Critical Graphs
cites work: An experimental comparison of four graph drawing algorithms.
cites work: On-line maintenance of triconnected components with SPQR-trees
cites work: On-Line Planarity Testing
cites work: A linear algorithm for the maximal planar subgraph problem
cites work: Edge crossings in drawings of bipartite graphs
cites work: Computing an st-numbering
cites work: Q4198056
cites work: Crossing Number is NP-Complete
cites work: Computing crossing numbers in quadratic time
cites work: Graph Drawing
cites work: Q4472293
cites work: Inserting an edge into a planar graph
cites work: Q5661522
cites work: Efficient Planarity Testing
cites work: Computing and Combinatorics
cites work: Maximum planar subgraphs and nice embeddings: Practical layout tools
cites work: The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization
cites work: Improved Bounds for the Crossing Numbers of Km,n and Kn
cites work: Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
cites work: String graphs. II: Recognizing string graphs is NP-hard
cites work: Alpha-algorithms for incremental planarity testing (extended abstract)
cites work: Q3866146
cites work: Crossing minimization in linear embeddings of graphs
cites work: Q4501703
cites work: Graphs drawn with few crossings per edge
cites work: Q5821653
DBLP publication ID: journals/disopt/BuchheimCEGJKMW08
DOI: 10.1016/J.DISOPT.2007.05.006
description: scientific article; zbMATH DE number 5358797