Dominating Sets in Chordal Graphs
From MaRDI portal
Publication:3944643
DOI10.1137/0211015zbMath0485.05055OpenAlexW2073279057MaRDI QIDQ3944643
J. Howard Johnson, Kellogg S. Booth
Publication date: 1982
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0211015
chordal graphundirected path graphsminimum dominating setgraph isomorphism problemdirected path graphslinear time greedy algorithm
Related Items (96)
On the Algorithmic Complexity of Total Domination ⋮ The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs ⋮ A linear algorithm for finding a minimum dominating set in a cactus ⋮ The neighborhood polynomial of chordal graphs ⋮ Tree-decompositions with bags of small diameter ⋮ The \(k\)-neighbor, \(r\)-domination problems on interval graphs ⋮ On the algorithmic complexity of edge total domination ⋮ Parameterized dominating set problem in chordal graphs: Complexity and lower bound ⋮ Clique tree generalization and new subclasses of chordal graphs ⋮ Some parallel algorithms on interval graphs ⋮ The diversity of domination ⋮ Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage ⋮ On the domatic number of interval graphs ⋮ A unified approach to domination problems on interval graphs ⋮ Structural parameterizations with modulator oblivion ⋮ STRONG DOUBLY GEODETIC PROBLEM ON GRAPHS ⋮ Total domination in interval graphs revisited ⋮ Bounds for the connected domination number of maximal outerplanar graphs ⋮ Labeling algorithms for domination problems in sun-free chordal graphs ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Algorithmic aspects of the generalized clique-transversal problem on chordal graphs ⋮ The algorithmic complexity of minus domination in graphs ⋮ Total domination in block graphs ⋮ On strictly chordality-\(k\) graphs ⋮ A width parameter useful for chordal and co-comparability graphs ⋮ The Neighborhood Polynomial of Chordal Graphs ⋮ Algorithmic Aspects of Disjunctive Total Domination in Graphs ⋮ Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs ⋮ A Dynamic Programming Approach to the Dominating Set Problem on k-Trees ⋮ On the tractability of optimization problems on \(H\)-graphs ⋮ On 3-degree 4-chordal graphs ⋮ Defending the Roman Empire from multiple attacks ⋮ Algorithm and hardness results on neighborhood total domination in graphs ⋮ On defensive alliances and strong global offensive alliances ⋮ The weighted perfect domination problem ⋮ On the vertices belonging to all, some, none minimum dominating set ⋮ Unnamed Item ⋮ Computing a minimum outer-connected dominating set for the class of chordal graphs ⋮ A linear time algorithm for liar's domination problem in proper interval graphs ⋮ Unnamed Item ⋮ Faster algorithms for vertex partitioning problems parameterized by clique-width ⋮ R-domination of block graphs ⋮ Chordal graphs and upper irredundance, upper domination and independence ⋮ Dominating sets in perfect graphs ⋮ Permutation graphs: Connected domination and Steiner trees ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ On total \(f\)-domination: polyhedral and algorithmic results ⋮ Mutual transferability for \((F, B, R)\)-domination on strongly chordal graphs and cactus graphs ⋮ An optimal algorithm for finding dominating cycles in circular-arc graphs ⋮ Dominating cliques in graphs ⋮ On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size ⋮ Efficient algorithms for shortest distance queries on special classes of polygons ⋮ A simple linear time algorithm for the domatic partition problem on strongly chordal graphs ⋮ Minimum dominating sets of intervals on lines ⋮ Two algorithms for determining a minimum independent dominating set ⋮ Improved algorithms and complexity results for power domination in graphs ⋮ Total domination in interval graphs ⋮ Shiftable intervals ⋮ Optimization problems in multiple subtree graphs ⋮ The algorithmic complexity of mixed domination in graphs ⋮ Some remarks on the geodetic number of a graph ⋮ The complexity of domination problems in circle graphs ⋮ Paired-domination problem on distance-hereditary graphs ⋮ Dominating cliques in graphs ⋮ Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes ⋮ Intersection graphs of non-crossing paths ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ On the geodetic and geodetic domination numbers of a graph ⋮ On \(f\)-domination: polyhedral and algorithmic results ⋮ Dominating set of rectangles intersecting a straight line ⋮ Vector domination in split-indifference graphs ⋮ On \(H\)-topological intersection graphs ⋮ The strong domination problem in block graphs and proper interval graphs ⋮ Roman \(\{k\}\)-domination in trees and complexity results for some classes of graphs ⋮ Weighted Upper Edge Cover: Complexity and Approximability ⋮ Distance Domination in Graphs ⋮ Defending the Roman Empire---a new strategy ⋮ New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs ⋮ An improved exact algorithm for minimum dominating set in chordal graphs ⋮ The semitotal domination problem in block graphs ⋮ Total Roman {2}-domination in graphs ⋮ On the algorithmic complexity of twelve covering and independence parameters of graphs ⋮ Real and integer domination in graphs ⋮ Domination problems on P5-free graphs ⋮ Domination, independent domination, and duality in strongly chordal graphs ⋮ Revising Johnson's table for the 21st century ⋮ Dominating sets for split and bipartite graphs ⋮ Algorithmic aspects of k-part degree restricted domination in graphs ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems) ⋮ Co-Roman domination in graphs ⋮ INVERSE ROMAN DOMINATION IN GRAPHS ⋮ Counting labelled chordal graphs ⋮ On the complexity of \(\{k\}\)-domination and \(k\)-tuple domination in graphs ⋮ Dominating sets and domatic number of circular arc graphs ⋮ Clustering and domination in perfect graphs ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters
This page was built for publication: Dominating Sets in Chordal Graphs
