A branch-and-price-and-cut method for computing an optimal bramble

DOI10.1016/j.disopt.2015.09.005zbMath1387.90281OpenAlexW2128439956MaRDI QIDQ1751138

J. Cole Smith, Sibel B. Sonuc, Illya V. Hicks

Publication date: 24 May 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2015.09.005

zbMATH Keywords

integer programmingtreewidthbranch-and-pricebramble

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Possible and Impossible Attempts to Solve the Treewidth Problem via ILPs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial algorithms for the maximum \(k\)-plex problem
• Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems
• Graph-based data clustering with overlaps
• Graph minors. XX: Wagner's conjecture
• Achievable sets, brambles, and sparse treewidth obstructions
• Treewidth lower bounds with brambles
• Satisfactory graph partition, variants, and generalizations
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Cliques and clustering: A combinatorial approach
• Graph searching and a min-max theorem for tree-width
• Pruning by isomorphism in branch-and-cut
• Exploiting orbits in symmetric ILP
• Algorithmic approach to the satisfactory graph partitioning problem
• An exact algorithm for the maximum \(k\)-club problem in an undirected graph
• A class of web-based facets for the generalized vertex packing problem
• Generalized network design problems.
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• On clique relaxation models in network analysis
• Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
• Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement
• A polyhedral study of the generalized vertex packing problem
• On tree width, bramble size, and expansion
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• On planar graphs with large tree-width and small grid minors
• Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
• Improving Discrete Model Representations via Symmetry Considerations
• The Structure and Number of Obstructions to Treewidth
• Easy problems for tree-decomposable graphs
• Constraint Orbital Branching
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• A graph‐theoretic generalization of the clique concept
• A New Lower Bound for Tree-Width Using Maximum Cardinality Search
• Linear-time computation of optimal subgraphs of decomposable graphs
• Solving partial constraint satisfaction problems with tree decomposition
• On Achieving Local View Capacity Via Maximal Independent Graph Scheduling
• Contraction and Treewidth Lower Bounds
• Orbital Branching

This page was built for publication: A branch-and-price-and-cut method for computing an optimal bramble