Approximation algorithms for cycle and path partitions in complete graphs
From MaRDI portal
Signed and weighted graphs (05C22) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)
Cites work
- 8/7-approximation algorithm for (1,2)-TSP
- A 4/5 -- approximation algorithm for the maximum traveling salesman problem
- A \(\frac78\)-approximation algorithm for metric Max TSP
- A \(d/2\) approximation for maximum weight independent set in \(d\)-claw free graphs
- A deterministic approximation algorithm for metric triangle packing
- A local search algorithm for binary maximum 2-path partitioning
- A randomized approximation algorithm for metric triangle packing
- An approximation algorithm for maximum packing of 3-edge paths
- An approximation algorithm for maximum triangle packing
- An improved approximation for maximum weighted \(k\)-set packing
- An improved randomized approximation algorithm for maximum triangle packing
- Approximation algorithms for maximum dispersion
- Approximation algorithms for the maximum-weight cycle/path packing problems
- Approximation results for the weighted \(P_4\) partition problem
- Deterministic 7/8-approximation for the metric maximum TSP
- Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems
- Erratum to: ``An improved randomized approximation algorithm for maximum triangle packing
- scientific article; zbMATH DE number 3643026 (Why is no real title available?)
- Improved approximation algorithms for cycle and path packings
- Improved approximation algorithms for metric MaxTSP
- Improved approximation algorithms for weighted 2-path partitions
- On Approximating Restricted Cycle Covers
- On local search for weighted \(k\)-set packing
- On the completeness of a generalized matching problem
- Passing the limits of pure local search for weighted \(k\)-Set packing
- The design of approximation algorithms
- The limits of local search for weighted \(k\)-set packing
This page was built for publication: Approximation algorithms for cycle and path partitions in complete graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7033930)
