Parameterized Complexity of Minimum Membership Dominating Set

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Parameterized Complexity of Minimum Membership Dominating Set

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Parameterized Complexity of Minimum Membership Dominating Set

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

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

—

Počet stran výsledku

12

Strana od-do

288-299

Název nakladatele

Springer

Místo vydání

Cham

Místo konání akce

Jember

Datum konání akce

24. 3. 2022

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—