Computational study on a PTAS for planar dominating set problem (Q1736542)

From MaRDI portal
Revision as of 07:00, 11 December 2024 by Import241208061232 (talk | contribs) (Normalize DOI.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Computational study on a PTAS for planar dominating set problem
scientific article

    Statements

    Computational study on a PTAS for planar dominating set problem (English)
    0 references
    0 references
    0 references
    0 references
    26 March 2019
    0 references
    Summary: The dominating set problem is a core NP-hard problem in combinatorial optimization and graph theory, and has many important applications. \textit{B. S. Baker} [J. Assoc. Comput. Mach. 41, No. 1, 153--180 (1994; Zbl 0807.68067)] introduces a \(k\)-outer planar graph decomposition-based framework for designing polynomial time approximation scheme (PTAS) for a class of NP-hard problems in planar graphs. It is mentioned that the framework can be applied to obtain an \(O(2^{ck}n)\) time, \(c\) is a constant, \((1+1/k)\)-approximation algorithm for the planar dominating set problem. We show that the approximation ratio achieved by the mentioned application of the framework is not bounded by any constant for the planar dominating set problem. We modify the application of the framework to give a PTAS for the planar dominating set problem. With \(k\)-outer planar graph decompositions, the modified PTAS has an approximation ratio \((1+2/k)\). Using \(2 k\)-outer planar graph decompositions, the modified PTAS achieves the approximation ratio \((1+1/k)\) in \(O(2^{2ck}n)\) time. We report a computational study on the modified PTAS. Our results show that the modified PTAS is practical.
    0 references
    dominating set problem
    0 references
    PTAS
    0 references
    branch-decomposition-based algorithms
    0 references
    planar graphs
    0 references
    computational study
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references