A branch-and-cut algorithm for the maximum covering cycle problem

DOI10.1007/S10479-018-2856-5MaRDI QIDQ2288980zbMATH OpenOpenAlexWikidataFDO

Authors Eduardo Álvarez-Miranda, Markus Sinnl

Publication date 20 January 2020

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10479-018-2856-5

zbMATH Keywords

branch-and-cutcovering problemsdomination problemsoptimal cycle problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Recommendations

• Branch-and-cut algorithms for the covering salesman problem
• A branch-and-bound algorithm for solving max-\(k\)-cut problem
• Approximation Algorithms for Min-Max Cycle Cover Problems
• An algorithm for the polyhedral cycle cover problem with constraints on the number and length of cycles
• An exact algorithm for the maximal covering problem
• Searching for a cycle with maximum coverage in undirected graphs
• A branch and bound algorithm for the maximum clique problem
• A branch and bound algorithm for the maximum clique problem
• On approximating maximum covering cycles in undirected graphs
• Approximation algorithm for min-max cycle cover problem on a mixed graph

Cites work

• scientific article; zbMATH DE number 1236360 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem
• A node-based ILP formulation for the node-weighted dominating Steiner problem
• An algorithmic framework for the exact solution of tree-star problems
• Approximation algorithms for the Geometric Covering Salesman Problem
• Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem
• Domination in graphs with bounded propagation: Algorithms, formulations and hardness results
• MIP models for connected facility location: a theoretical and computational study
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Permutation graphs: Connected domination and Steiner trees
• Searching for a cycle with maximum coverage in undirected graphs
• Solution of a Large-Scale Traveling-Salesman Problem
• Solving Steiner tree problems in graphs to optimality
• Solving the Orienteering Problem through Branch-and-Cut
• The Asymmetric Assignment Problem and Some New Facets of the Traveling Salesman Polytope on a Directed Graph
• The Covering Salesman Problem
• The Covering Tour Problem
• The bi-objective covering tour problem
• The generalized covering salesman problem
• The median tour and maximal covering tour problems: Formulations and heuristics
• Thinning out Steiner trees: a node-based model for uniform edge costs
• Time constrained maximal covering salesman problem with weighted demands and partial coverage

Cited in

(11)

• An exact algorithm for the maximal covering problem
• Metaheuristics for the distance constrained generalized covering traveling salesman problem
• Covering a graph with cycles.
• A branch-and-bound algorithm for solving max-\(k\)-cut problem
• Minimum constellation covers: hardness, approximability and polynomial cases
• A branch-and-cut algorithm for the minimum labeling Hamiltonian cycle problem and two variants
• Branch-and-cut algorithms for the covering salesman problem
• Searching for a cycle with maximum coverage in undirected graphs
• An optimal strategy for the constrained cycle cover problem
• Exact algorithms for budgeted prize-collecting covering subgraph problems
• A branch-and-cut algorithm for the plant-cycle location problem

Describes a project that uses

Uses Software

• SteinLib

This page was built for publication: A branch-and-cut algorithm for the maximum covering cycle problem

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