Approximating the tree and tour covers of a graph
From MaRDI portal
Publication:688437
DOI10.1016/0020-0190(93)90072-HzbMATH Open0785.68041MaRDI QIDQ688437FDOQ688437
Authors: Esther M. Arkin, Magnús M. Halldórsson, Refael Hassin 
Publication date: 16 January 1994
Published in: Information Processing Letters (Search for Journal in Brave)
Recommendations
- Improved approximations for tour and tree covers
- scientific article; zbMATH DE number 1670541
- Approximation algorithms for metric tree cover and generalized tour and tree covers
- The approximability of partial vertex covers in trees
- Approximating the minimum tour cover of a digraph
- On the tree cover number of a graph
- On covering vertices of a graph by trees
- Approximating the minmax rooted-tree cover in a tree
- Approximation algorithms for generalized bounded tree cover
- Generalized bounded tree cover of a graph
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Title not available (Why is that?)
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Title not available (Why is that?)
- A note on the prize collecting traveling salesman problem
- `` Strong NP-Completeness Results
- Title not available (Why is that?)
- Ramsey numbers and an approximation algorithm for the vertex cover problem
- Efficient probabilistically checkable proofs and applications to approximations
- Approximate algorithms for the travelling purchaser problem
- A faster approximation algorithm for the Steiner problem in graphs
- The optimal location of a path or tree in a tree network
- Title not available (Why is that?)
- Optimum watchman routes
- The location of central structures in trees
- A faster approximation algorithm for the Steiner tree problem in graphs
- On locating path- or tree-shaped facilities on networks
- Optimal location of a path or tree on a network with cycles
- Location Of A Tree Shaped Facility In A Network
- A minimum length covering subgraph of a network
Cited In (33)
- A Primal-Dual Method for Approximating Tree Cover with Two Weights
- Complexity and algorithms for the connected vertex cover problem in 4-regular graphs
- An approximation algorithm for \(K\)-best enumeration of minimal connected edge dominating sets with cardinality constraints
- Approximability of the capacitated \(b\)-edge dominating set problem
- PTAS for connected vertex cover in unit disk graphs
- Approximating the minimum tour cover of a digraph
- On approximating (connected) 2-edge dominating set by a tree
- On approximating (connected) 2-edge dominating set by a tree
- A primal-dual method for approximating tree cover with two weights
- On approximability of the independent/connected edge dominating set problems
- A 2-approximation NC algorithm for connected vertex cover and tree cover
- Improved approximations for tour and tree covers
- On the tree cover number of a graph
- Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph
- Generalizing the induced matching by edge capacity constraints
- Complexity of minimum corridor guarding problems
- Approximating the Minimum Tour Cover with a Compact Linear Program
- Minimum-diameter covering problems
- Efficient algorithms for network localization using cores of underlying graphs
- Approximation algorithms for metric tree cover and generalized tour and tree covers
- Complexity of the minimum-length corridor problem
- Complexity and Approximation Results for the Connected Vertex Cover Problem
- A metaheuristic approach to the dominating tree problem
- Vertex and edge covers with clustering properties: Complexity and algorithms
- Better \(s-t\)-tours by Gao trees
- Selecting and covering colored points
- Circumventing connectivity for kernelization
- On approximation of dominating tree in wireless sensor networks
- Title not available (Why is that?)
- Title not available (Why is that?)
- Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
- A 2log2(n)-Approximation Algorithm for Directed Tour Cover
- Graph covering using bounded size subgraphs
This page was built for publication: Approximating the tree and tour covers of a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q688437)
