The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
From MaRDI portal
Publication:3697054
DOI10.1137/0605034zbMath0576.05054OpenAlexW2072141822MaRDI QIDQ3697054
Nemhauser, George I., Gerard Jennhwa Chang
Publication date: 1984
Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0605034
Integer programming (90C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (05C99)
Related Items
A linear time algorithm to solve the weighted perfect domination problem in series-parallel graphs, Lexbfs-orderings and powers of hhd-free graphs∗, Powers of hhd-free graphs∗, Pseudo-modular graphs, Tree spanners on chordal graphs: complexity and algorithms, On the algorithmic complexity of edge total domination, On the kernelization of split graph problems, The ratio of the distance irredundance and domination numbers of a graph, Radius versus diameter in cocomparability and intersection graphs, \(r\)-dominating cliques in graphs with hypertree structure, Local medians in chordal graphs, Powers of distance-hereditary graphs, Distance irredundance and connected domination numbers of a graph, STRONG DOUBLY GEODETIC PROBLEM ON GRAPHS, Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs, On diameters and radii of bridged graphs, Labeling algorithms for domination problems in sun-free chordal graphs, A faster diameter problem algorithm for a chordal graph, with a connection to its center problem, Algorithmic aspects of the generalized clique-transversal problem on chordal graphs, The weighted perfect domination problem and its variants, An algorithm to find two distance domination parameters in a graph, New characterizations of Gallai's \(i\)-triangulated graphs, Total domination in block graphs, The algorithmic use of hypertree structure and maximum neighbourhood orderings, Roman domination on strongly chordal graphs, Broadcast domination and multipacking in strongly chordal graphs, Covering, Packing and Generalized Perfection, Beyond Helly graphs: the diameter problem on absolute retracts, Extremal values on Zagreb indices of trees with given distance \(k\)-domination number, A linear-time algorithm for semitotal domination in strongly chordal graphs, Augmenting graphs to minimize the radius, Distance problems within Helly graphs and \(k\)-Helly graphs, Dually chordal graphs, Requiring adjacent chords in cycles, A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs, The weighted perfect domination problem, Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs, Rainbow domination and related problems on strongly chordal graphs, R-domination of block graphs, Representations of graphs and networks (coding, layouts and embeddings), Homogeneous sets and domination: A linear time algorithm for distance?hereditary graphs, Algorithmic aspects of clique-transversal and clique-independent sets, Centers of chordal graphs, Mutual transferability for \((F, B, R)\)-domination on strongly chordal graphs and cactus graphs, Distances in cocomparability graphs and their powers, On packing and covering numbers of graphs, Algorithm on rainbow connection for maximal outerplanar graphs, On the \(k\)-limited packing numbers in graphs, The algorithmic use of hypertree structure and maximum neighbourhood orderings, Total domination in interval graphs, Complexity of distance paired-domination problem in graphs, The algorithmic complexity of mixed domination in graphs, Distance domination-critical graphs, On probe permutation graphs, An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time, Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs, The degree-preserving spanning tree problem in strongly chordal and directed path graphs, A linear-time algorithm for paired-domination problem in strongly chordal graphs, An efficient algorithm for distance total domination in block graphs, The strong domination problem in block graphs and proper interval graphs, A one-to-one correspondence between colorings and stable sets, Chromatic numbers of competition graphs, Odd twists on strongly chordal graphs, \(k\)-tuple domination in graphs, Minimum Eccentricity Shortest Paths in Some Structured Graph Classes, Average distances and distance domination numbers, Packing and domination parameters in digraphs, Domination, independent domination, and duality in strongly chordal graphs, A characterization of strongly chordal graphs, Interpolation theorems for domination numbers of a graph, Characterizations of strongly chordal graphs, Strong Chordality of Graphs with Possible Loops, The minimum eccentric distance sum of trees with given distance k-domination number, Efficient \((j, k)\)-dominating functions, Bibliography on domination in graphs and some basic definitions of domination parameters, Vertex cover at distance on \(H\)-free graphs
Cites Work
- On rigid circuit graphs
- On powers and centers of chordal graphs
- R-domination of block graphs
- A linear algorithm for the domination number of a tree
- Relations between packing and covering numbers of a tree
- Optimum domination in weighted trees
- Bounds for the covering number of a graph
- A characterisation of rigid circuit graphs
- Incidence matrices and interval graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- An Algorithmic Approach to Network Location Problems. I: Thep-Centers
- Representations of chordal graphs as subtrees of a tree
- Dominating Sets in Chordal Graphs
- R -Domination in Graphs
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
