On f-domination: polyhedral and algorithmic results
Mauro Dell’Amico () and
José Neto ()
Additional contact information
Mauro Dell’Amico: University of Modena and Reggio Emilia
José Neto: Université Paris-Saclay
Mathematical Methods of Operations Research, 2019, vol. 90, issue 1, No 1, 22 pages
Abstract:
Abstract Given an undirected simple graph G with node set V and edge set E, let $$f_v$$ f v , for each node $$v \in V$$ v ∈ V , denote a nonnegative integer value that is lower than or equal to the degree of v in G. An f-dominating set in G is a node subset D such that for each node $$v\in V{{\setminus }}D$$ v ∈ V \ D at least $$f_v$$ f v of its neighbors belong to D. In this paper, we study the polyhedral structure of the polytope defined as the convex hull of all the incidence vectors of f-dominating sets in G and give a complete description for the case of trees. We prove that the corresponding separation problem can be solved in polynomial time. In addition, we present a linear-time algorithm to solve the weighted version of the problem on trees: Given a cost $$c_v\in {\mathbb {R}}$$ c v ∈ R for each node $$v\in V$$ v ∈ V , find an f-dominating set D in G whose cost, given by $$\sum _{v\in D}{c_v}$$ ∑ v ∈ D c v , is a minimum.
Keywords: Domination; Polyhedral combinatorics; Tree; Linear-time algorithm; 05C69; 51M20; 68Q25; 68R10; 90C10 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:
Downloads: (external link)
http://link.springer.com/10.1007/s00186-018-0650-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:90:y:2019:i:1:d:10.1007_s00186-018-0650-4
Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186
DOI: 10.1007/s00186-018-0650-4
Access Statistics for this article
Mathematical Methods of Operations Research is currently edited by Oliver Stein
More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().