Min-max tree covers of graphs.
From MaRDI portal
Publication:703232
DOI10.1016/j.orl.2003.11.010zbMath1054.90079OpenAlexW1974713906MaRDI QIDQ703232
R. Ravi, Jochen Könemann, Amitabh Sinha, Guy Even, Naveen Garg
Publication date: 11 January 2005
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.orl.2003.11.010
Programming involving graphs or networks (90C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Discrete location and assignment (90B80) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
A joint optimization of data ferry trajectories and communication powers of ground sensors for long-term environmental monitoring, A Fast $$(2 + 2/7)$$-Approximation Algorithm for Capacitated Cycle Covering, An overview of graph covering and partitioning, Approximating the minmax rooted-tree cover in a tree, Improved approximation algorithms for some min-max and minimum cycle cover problems, Improved Approximation Algorithms for Min-Max and Minimum Vehicle Routing Problems, On optimal coverage of a tree with multiple robots, Approximation algorithms for the min-max clustered \(k\)-traveling salesmen problems, Better approximability results for min-max tree/cycle/path cover problems, Graph covering using bounded size subgraphs, Covering directed graphs by in-trees, Covering Directed Graphs by In-Trees, Improved approximation algorithms for some min-max postmen cover problems with applications to the min-max subtree cover, Unnamed Item, Capacitated Vehicle Routing with Non-uniform Speeds, Min-max cover of a graph with a small number of parts, Improved approximation algorithms for the MIN-MAX tree cover and bounded tree cover problems, New approximation algorithms for the minimum cycle cover problem, Vehicle routing with subtours, Minimum makespan vehicle routing problem with compatibility constraints, Approximation hardness of min-max tree covers, New LP relaxations for minimum cycle/path/tree cover problems, Approximation results for min-max path cover problems in vehicle routing, Capacitated Vehicle Routing with Nonuniform Speeds, Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph, Approximation Algorithms for Generalized Bounded Tree Cover, An approximation algorithm for vehicle routing with compatibility constraints, The \(m\)-Steiner traveling salesman problem with online edge blockages, New approximation algorithms for the rooted budgeted cycle cover problem, Approximation algorithms for some minimum postmen cover problems, New approximation algorithms for the rooted budgeted cycle cover problem, Minmax Tree Cover in the Euclidean Space, Distributed boundary coverage with a team of networked miniature robots using a robust market-based algorithm, Multiple UAV exploration of an unknown region, Approximation results for a min-max location-routing problem, Continuous graph partitioning for camera network surveillance, A fast \((2 + \frac{2}{7})\)-approximation algorithm for capacitated cycle covering
Uses Software
Cites Work
