On f-domination: polyhedral and algorithmic results

DOI10.1007/S00186-018-0650-4MaRDI QIDQ2274147zbMATH OpenOpenAlexWikidataFDO

Authors Mauro Dell'Amico, José Neto

Publication date 19 September 2019

Published in Mathematical Methods of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00186-018-0650-4

zbMATH Keywords

treepolyhedral combinatoricsdominationlinear-time algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Polyhedra and polytopes; regular figures, division of spaces (51M20)

Recommendations

• On total \(f\)-domination: polyhedral and algorithmic results
• A polyhedral view to a generalization of multiple domination
• Algorithmic aspects of \(\mathcal{F}\)-domination in graphs
• A polyhedral view to generalized multiple domination and limited packing
• On $f$-domination number of a graph

Cites work

• scientific article; zbMATH DE number 3918387 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• scientific article; zbMATH DE number 1559541 (Why is no real title available?)
• A linear algorithm for finding a minimum dominating set in a cactus
• A linear algorithm for the domination number of a series-parallel graph
• A new domination conception
• Approximating fault-tolerant domination in general graphs
• Approximation hardness of dominating set problems in bounded degree graphs
• Dominating Sets in Chordal Graphs
• Domination, independent domination, and duality in strongly chordal graphs
• Facet of regular 0–1 polytopes
• Linear Separation of Dominating Sets in Graphs
• New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs
• On $f$-domination number of a graph
• On certain polytopes associated with graphs
• On the dominating set polytope
• On the total \(k\)-domination in graphs
• On total \(f\)-domination: polyhedral and algorithmic results
• One-node cutsets and the dominating set polytope
• Optimum domination in weighted trees
• Perfect zero–one matrices
• Polytope Des Absorbants Dans Une Classe De Graphe a Seuil
• Properties of vertex packing and independence system polyhedra
• The dominating set polytope via facility location
• The ellipsoid method and its consequences in combinatorial optimization
• The k-neighbor domination problem
• The set covering problem on circulant matrices: polynomial instances and the relation with the dominating set problem on webs
• Time bounds for selection
• Total domination in graphs
• Upper bounds for \(f\)-domination number of graphs

Cited in

(4)

• Algorithmic aspects of \(\mathcal{F}\)-domination in graphs
• A polyhedral view to a generalization of multiple domination
• On total \(f\)-domination: polyhedral and algorithmic results
• Facets of the dynamic monopoly polytope: linear ordering formulation

This page was built for publication: On \(f\)-domination: polyhedral and algorithmic results

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2274147)