The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
From MaRDI portal
Publication:3697054
DOI10.1137/0605034zbMATH Open0576.05054OpenAlexW2072141822MaRDI QIDQ3697054FDOQ3697054
Authors: G. L. Nemhauser, 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
Recommendations
Integer programming (90C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (05C99)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Incidence matrices and interval graphs
- Title not available (Why is that?)
- On rigid circuit 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
- Title not available (Why is that?)
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- A linear algorithm for the domination number of a tree
- Dominating Sets in Chordal Graphs
- Relations between packing and covering numbers of a tree
- Title not available (Why is that?)
- Title not available (Why is that?)
- A characterisation of rigid circuit graphs
- Optimum domination in weighted trees
- On powers and centers of chordal graphs
- R -Domination in Graphs
- Title not available (Why is that?)
- R-domination of block graphs
- Bounds for the covering number of a graph
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (80)
- Algorithmic aspects of clique-transversal and clique-independent sets
- An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time
- A one-to-one correspondence between colorings and stable sets
- A linear-time algorithm for paired-domination problem in strongly chordal graphs
- Labeling algorithms for domination problems in sun-free chordal graphs
- Pseudo-modular graphs
- A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs
- On probe permutation graphs
- Total domination in block graphs
- Roman domination on strongly chordal graphs
- A linear time algorithm to solve the weighted perfect domination problem in series-parallel graphs
- On the \(k\)-limited packing numbers in graphs
- Mutual transferability for \((F, B, R)\)-domination on strongly chordal graphs and cactus graphs
- Bibliography on domination in graphs and some basic definitions of domination parameters
- Average distances and distance domination numbers
- The degree-preserving spanning tree problem in strongly chordal and directed path graphs
- A characterization of strongly chordal graphs
- Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs
- Homogeneous sets and domination: A linear time algorithm for distance-hereditary graphs
- Distance irredundance and connected domination numbers of a graph
- Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs
- On the algorithmic complexity of edge total domination
- Characterizations of strongly chordal graphs
- The algorithmic complexity of mixed domination in graphs
- Complexity of distance paired-domination problem in graphs
- Domination, independent domination, and duality in strongly chordal graphs
- The algorithmic use of hypertree structure and maximum neighbourhood orderings
- Lexbfs-orderings and powers of hhd-free graphs∗
- Centers of chordal graphs
- The weighted perfect domination problem
- Tree spanners on chordal graphs: complexity and algorithms
- \(k\)-tuple domination in graphs
- An algorithm to find two distance domination parameters in a graph
- On diameters and radii of bridged graphs
- Dually chordal graphs
- Powers of hhd-free graphs∗
- Covering, Packing and Generalized Perfection
- Local medians in chordal graphs
- Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
- STRONG DOUBLY GEODETIC PROBLEM ON GRAPHS
- Distances in cocomparability graphs and their powers
- Packing and domination parameters in digraphs
- A linear-time algorithm for semitotal domination in strongly chordal graphs
- Extremal values on Zagreb indices of trees with given distance \(k\)-domination number
- On packing and covering numbers of graphs
- Powers of distance-hereditary graphs
- The weighted perfect domination problem and its variants
- Total domination in interval graphs
- Radius versus diameter in cocomparability and intersection graphs
- Augmenting graphs to minimize the radius
- Distance domination-critical graphs
- \(r\)-dominating cliques in graphs with hypertree structure
- Rainbow domination and related problems on strongly chordal graphs
- Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs
- Algorithm on rainbow connection for maximal outerplanar graphs
- The minimum eccentric distance sum of trees with given distance \(k\)-domination number
- Chromatic numbers of competition graphs
- R-domination of block graphs
- Interpolation theorems for domination numbers of a graph
- The ratio of the distance irredundance and domination numbers of a graph
- Representations of graphs and networks (coding, layouts and embeddings)
- Broadcast domination and multipacking in strongly chordal graphs
- Odd twists on strongly chordal graphs
- Efficient \((j, k)\)-dominating functions
- Vertex cover at distance on \(H\)-free graphs
- Requiring adjacent chords in cycles
- Leanness computation: small values and special graph classes
- On the kernelization of split graph problems
- A faster diameter problem algorithm for a chordal graph, with a connection to its center problem
- On the complexity of finding a sun in a graph
- The algorithmic use of hypertree structure and maximum neighbourhood orderings
- An efficient algorithm for distance total domination in block graphs
- Beyond Helly graphs: the diameter problem on absolute retracts
- Distance problems within Helly graphs and \(k\)-Helly graphs
- New characterizations of Gallai's \(i\)-triangulated graphs
- Minimum eccentricity shortest paths in some structured graph classes
- The strong domination problem in block graphs and proper interval graphs
- Homogeneous sets and domination problems
- LexBFS-orderings and powers of graphs
- Strong Chordality of Graphs with Possible Loops
This page was built for publication: The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3697054)
