Approximating the tree and tour covers of a graph
From MaRDI portal
Publication:688437
DOI10.1016/0020-0190(93)90072-HzbMath0785.68041MaRDI QIDQ688437
Magnús M. Halldórsson, Refael Hassin, Esther M. Arkin
Publication date: 16 January 1994
Published in: Information Processing Letters (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)
Related Items
On approximating (connected) 2-edge dominating set by a tree, A 2-approximation NC algorithm for connected vertex cover and tree cover, Approximating the Minimum Tour Cover with a Compact Linear Program, Complexity of the minimum-length corridor problem, A metaheuristic approach to the dominating tree problem, Graph covering using bounded size subgraphs, Complexity and Approximation Results for the Connected Vertex Cover Problem, Circumventing connectivity for kernelization, On approximation of dominating tree in wireless sensor networks, Complexity of minimum corridor guarding problems, Approximability of the capacitated \(b\)-edge dominating set problem, Complexity and algorithms for the connected vertex cover problem in 4-regular graphs, Approximating the minimum tour cover of a digraph, Approximation algorithms for metric tree cover and generalized tour and tree covers, A primal-dual method for approximating tree cover with two weights, Generalizing the induced matching by edge capacity constraints, On Approximating (Connected) 2-Edge Dominating Set by a Tree, Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs, Minimum-diameter covering problems, Selecting and covering colored points, Efficient algorithms for network localization using cores of underlying graphs, Vertex and edge covers with clustering properties: Complexity and algorithms, PTAS for connected vertex cover in unit disk graphs, Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph, A Primal-Dual Method for Approximating Tree Cover with Two Weights, On approximability of the independent/connected edge dominating set problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on the prize collecting traveling salesman problem
- Ramsey numbers and an approximation algorithm for the vertex cover problem
- A minimum length covering subgraph of a network
- The location of central structures in trees
- Optimum watchman routes
- A faster approximation algorithm for the Steiner tree problem in graphs
- Approximate algorithms for the travelling purchaser problem
- On locating path- or tree-shaped facilities on networks
- Optimal location of a path or tree on a network with cycles
- The optimal location of a path or tree in a tree network
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- `` Strong NP-Completeness Results
- Efficient probabilistically checkable proofs and applications to approximations
- Location Of A Tree Shaped Facility In A Network
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- A faster approximation algorithm for the Steiner problem in graphs
