Approximation Schemes for Bounded Distance Problems on Fractionally Treewidth-Fragile Graphs.
From MaRDI portal
Abstract: We give polynomial-time approximation schemes for monotone maximization problems expressible in terms of distances (up to a fixed upper bound) and efficiently solvable in graphs of bounded treewidth. These schemes apply in all fractionally treewidth-fragile graph classes, a property that is true for many natural graph classes with sublinear separators. We also provide quasipolynomial-time approximation schemes for these problems in all classes with sublinear separators.
Recommendations
- scientific article; zbMATH DE number 238431
- Approximation algorithms for fragmenting a graph against a stochastically-located threat
- Approximation algorithms for fragmenting a graph against a stochastically-located threat
- Fractional distance domination in graphs
- Approximating sparsest cut in graphs of bounded treewidth
- Optimal approximation algorithms for maximum distance-bounded subgraph problems
- Optimal approximation algorithms for maximum distance-bounded subgraph problems
- Tight approximation bounds for combinatorial frugal coverage algorithms
- Approximation algorithms for approximating graphs with bounded number of connected components
- Approximation algorithms for combinatorial fractional programming problems
Cited in
(2)
This page was built for publication: Approximation Schemes for Bounded Distance Problems on Fractionally Treewidth-Fragile Graphs.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6075929)
