Searching for a cycle with maximum coverage in undirected graphs

DOI10.1007/S11590-015-0952-XzbMATH Open1355.90083OpenAlexW2240776925MaRDI QIDQ331987FDOQ331987

Authors: Andrea Grosso, Fabio Salassa, Wim Vancroonenburg 

Publication date: 27 October 2016

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

Full work available at URL: http://hdl.handle.net/2318/1622326

Recommendations

• On approximating maximum covering cycles in undirected graphs
• A branch-and-cut algorithm for the maximum covering cycle problem
• Covering a graph with cycles.
• On the asymptotic optimality of a solution of the Euclidean problem of covering a graph by \(m\) nonadjacent cycles of maximum total weight
• Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles

zbMATH Keywords

heuristicsinteger programmingconstraint generationmaximum covering cycle

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Integer programming (90C10)

Cites Work

• On dominating and spanning circuits in graphs
• Local branching
• The Covering Tour Problem
• The Covering Salesman Problem
• Approximation algorithms for connected dominating sets
• Finding minimum dominating cycles in permutation graphs
• Existence of dominating cycles and paths
• Generating subtour elimination constraints for the TSP from pure integer solutions
• The generalized covering salesman problem
• On Spanning and Dominating Circuits in Graphs
• Improved convergent heuristics for the 0-1 multidimensional knapsack problem
• Solving connected dominating set faster than \(2^n\)

Cited In (6)

• Finding even cycles faster via capped k-walks
• Exact algorithms for budgeted prize-collecting covering subgraph problems
• Methods for determining cycles of a specific length in undirected graphs with edge weights
• A branch-and-cut algorithm for the maximum covering cycle problem
• On approximating maximum covering cycles in undirected graphs
• Approximating maximum weight cycle covers in directed graphs with weights zero and one

This page was built for publication: Searching for a cycle with maximum coverage in undirected graphs

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