University of Sussex
Browse

File(s) not publicly available

Approximation hardness of dominating set problems

presentation
posted on 2023-06-08, 05:18 authored by Miroslav ChlebikMiroslav Chlebik, Janka Chlebíková
We study approximation hardness of the MINIMUM DOMINATING SET problem and its variants in undirected and directed graphs. We state the first explicit approximation lower bounds for various kinds of domination problems (connected, total, independent) in bounded degree graphs. For most of dominating set problems we prove asymptotically almost tight lower bounds. The results are applied to improve the lower bounds for other related problems such as the MAXIMUM INDUCED MATCHING problem and the MAXIMUM LEAF SPANNING TREE problem.

History

Publication status

  • Published

ISSN

0302-9743

Publisher

Springer Berlin / Heidelberg

Volume

LNCS 3

Pages

12.0

Presentation Type

  • paper

Event name

12th Annual European Symposium on Algorithms (ESA 2004)

Event location

Bergen, NORWAY

Event type

conference

ISBN

978-3-540-23025-0

Department affiliated with

  • Mathematics Publications

Notes

Lecture Notes in Computer Science, Algorithms ESA 2004

Full text available

  • No

Peer reviewed?

  • Yes

Editors

T Radzik, S Albers

Legacy Posted Date

2012-02-06

Usage metrics

    University of Sussex (Publications)

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC