On f-domination: polyhedral and algorithmic results

DOI10.1007/S00186-018-0650-4zbMATH Open1419.05166OpenAlexW2897721402WikidataQ129055896 ScholiaQ129055896MaRDI QIDQ2274147FDOQ2274147

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

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

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)

Cites Work

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

Cited In (2)

• A polyhedral view to a generalization of multiple domination
• 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)