Total Domination and Irredundance in Weighted Interval Graphs

DOI10.1137/0401032zbMath0648.05041OpenAlexW1969415257MaRDI QIDQ3792718

Alessandro Gori, Alan A. Bertossi

Publication date: 1988

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0401032

zbMATH Keywords

algorithmweighted graphsinterval graphtotal dominating setirredundant setmin-treeminimum weighted maximal irredundant setminimum weighted total dominating set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Optimality conditions (49K99)

Related Items

Tree-decompositions with bags of small diameter, Determining DNA sequence similarity using maximum independent set algorithms for interval graphs, Irredundance perfect graphs, On the domatic number of interval graphs, Weighted independent perfect domination on cocomparability graphs, On total \(f\)-domination: polyhedral and algorithmic results, An optimal algorithm to find minimum k-hop dominating set of interval graphs, Connected domination and Steiner set on weighted permutation graphs, Minimum dominating sets of intervals on lines, Incorporating negative-weight vertices in certain vertex-search graph algorithms, Irredundancy in circular arc graphs, Efficient algorithms for the conditional covering problem, Integer linear programming models for the weighted total domination problem, Enumeration and maximum number of maximal irredundant sets for chordal graphs, A survey of selected recent results on total domination in graphs, An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs, Weighted irredundance of interval graphs., Bibliography on domination in graphs and some basic definitions of domination parameters