Parameterized Complexity of Minimum Membership Dominating Set
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F22%3A00358548" target="_blank" >RIV/68407700:21240/22:00358548 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1007/978-3-030-96731-4_24" target="_blank" >https://doi.org/10.1007/978-3-030-96731-4_24</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-030-96731-4_24" target="_blank" >10.1007/978-3-030-96731-4_24</a>
Alternative languages
Result language
angličtina
Original language name
Parameterized Complexity of Minimum Membership Dominating Set
Original language description
Given a graph G = (V,E) and an integer k, the Minimum Membership Dominating Set (MMDS) problem seeks to find a dominating set S ? V of G such that for each v element V , |N[v] ∩ S| is at most k. We investigate the parameterized complexity of the problem and obtain the following results about MMDS: 1. W[1]-hardness of the problem parameterized by the pathwidth (and thus, treewidth) of the input graph. 2. W[1]-hardness parameterized by k on split graphs. 3. An algorithm running in time 2^O(vc) |V |^O(1), where vc is the size of a minimum-sized vertex cover of the input graph. 4. An ETH-based lower bound showing that the algorithm mentioned in the previous item is optimal.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
WALCOM: Algorithms and Computation - 16th International Conference and Workshops, WALCOM 2022, Jember, Indonesia, March 24-26, 2022, Proceedings
ISBN
978-3-030-96730-7
ISSN
0302-9743
e-ISSN
—
Number of pages
12
Pages from-to
288-299
Publisher name
Springer
Place of publication
Cham
Event location
Jember
Event date
Mar 24, 2022
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—