Domination, independent domination, and duality in strongly chordal graphs
From MaRDI portal
Publication:788002
DOI10.1016/0166-218X(84)90061-1zbMath0531.05045MaRDI QIDQ788002
Publication date: 1984
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
strongly chordal graphs; independent dominating sets; totally balanced matrices; minimum weight dominating sets
68Q25: Analysis of algorithms and problem complexity
90C10: Integer programming
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Related Items
CONVEXITY OF MINIMAL DOMINATING FUNCTIONS OF TREES: A SURVEY, Unnamed Item, EXTREMUM AGGREGATES OF MINIMAL 0-DOMINATING FUNCTIONS OF GRAPHS, Total domination in interval graphs, Which claw-free graphs are perfectly orderable?, A linear algorithm for the group path problem on chordal graphs, On the computational complexity of upper fractional domination, Bibliography on domination in graphs and some basic definitions of domination parameters, Independent domination in hereditary classes, Domination in convex and chordal bipartite graphs, On \(P_4\)-transversals of chordal graphs, On the parameterized complexity of multiple-interval graph problems, Characterizations of strongly chordal graphs, Location problems, Dominating sets and domatic number of circular arc graphs, A linear algorithm for finding a minimum dominating set in a cactus, Forbidden submatrices, Totally balanced and totally unimodular matrices defined by center location problems, A unified approach to domination problems on interval graphs, Labeling algorithms for domination problems in sun-free chordal graphs, Total domination in block graphs, Generalized domination and efficient domination in graphs, Independent domination in chordal graphs, Dominating sets in perfect graphs, Permutation graphs: Connected domination and Steiner trees, An optimal algorithm for finding dominating cycles in circular-arc graphs, A simple linear time algorithm for the domatic partition problem on strongly chordal graphs, An optimal parallel algorithm for the domatic partition problem on an interval graph given its sorted model, Strong elimination ordering of the total graph of a tree, Linear algorithm for domatic number problem on interval graphs, Weighted connected domination and Steiner trees in distance-hereditary graphs, Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms, On the algorithmic complexity of twelve covering and independence parameters of graphs, Construction of a simple elimination scheme for a chordal comparability graph in linear time, Recognizing clique graphs of directed and rooted path graphs, Real and integer domination in graphs, The domatic number problem on some perfect graph families, Dominating cliques in chordal graphs, The domatic number problem, Fractional domination of strong direct products, A parallel algorithm for computing Steiner trees in strongly chordal graphs, The parallel solution of domination problems on chordal and strongly chordal graphs, Characterizations of two classes of digraphs, The bondage and reinforcement numbers of \(\gamma_ f\) for some graphs, \(r\)-dominating cliques in graphs with hypertree structure, One-node cutsets and the dominating set polytope, Transversal partitioning in balanced hypergraphs, The algorithmic use of hypertree structure and maximum neighbourhood orderings, The bottleneck independent domination on the classes of bipartite graphs and block graphs., The domatic number of block-cactus graphs, A characterization of strongly chordal graphs, Domination and total domination on asteroidal triple-free graphs, Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs, Algorithmic aspects of clique-transversal and clique-independent sets, On the independent dominating set polytope, On the dominating set polytope, Strongly simplicial vertices of powers of trees, Polar SAT and related graphs, Shiftable intervals, The topology of the independence complex, Independent Domination in Triangle Graphs, On the Algorithmic Complexity of Total Domination, Convexity in Graphs and Hypergraphs, Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Characterizations of strongly chordal graphs
- Independent domination in chordal graphs
- A linear algorithm for the domination number of a tree
- Optimum domination in weighted trees
- Triangulated graphs and the elimination process
- Characterizations of totally balanced matrices
- Totally-Balanced and Greedy Matrices
- The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
- Dominating Sets in Chordal Graphs
- R -Domination in Graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Towards a theory of domination in graphs
- Balanced matrices
