Domination, independent domination, and duality in strongly chordal graphs

DOI10.1016/0166-218X(84)90061-1zbMath0531.05045OpenAlexW2050228489WikidataQ127740357 ScholiaQ127740357MaRDI QIDQ788002

Publication date: 1984

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(84)90061-1

zbMATH Keywords

strongly chordal graphs independent dominating sets totally balanced matrices minimum weight dominating sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (only showing first 100 items - show all)

Independent domination in directed graphs ⋮ A tight relation between series-parallel graphs and bipartite distance hereditary graphs ⋮ Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs ⋮ Deferred-query—An efficient approach for problems on interval and circular-arc graphs ⋮ CONVEXITY OF MINIMAL DOMINATING FUNCTIONS OF TREES: A SURVEY ⋮ Unnamed Item ⋮ A linear-time algorithm for semitotal domination in strongly chordal graphs ⋮ Mobility offer allocations in corporate settings ⋮ Strong Cocomparability Graphs and Slash-Free Orderings of Matrices ⋮ Unnamed Item ⋮ EXTREMUM AGGREGATES OF MINIMAL 0-DOMINATING FUNCTIONS OF GRAPHS ⋮ Total domination in interval graphs ⋮ The algorithmic use of hypertree structure and maximum neighbourhood orderings ⋮ A linear‐time algorithm for broadcast domination in a tree ⋮ Common extremal graphs for three inequalities involving domination parameters ⋮ Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs ⋮ Approximation hardness of domination problems on generalized convex graphs ⋮ Weighted Upper Edge Cover: Complexity and Approximability ⋮ It Is All Labeling ⋮ Strong Chordality of Graphs with Possible Loops ⋮ Linear programming approach for various domination parameters ⋮ Semi-dynamic algorithms for strongly chordal graphs ⋮ Broadcast domination and multipacking: bounds and the integrality gap ⋮ Independent domination in hereditary classes ⋮ On the Algorithmic Complexity of Total Domination ⋮ A linear algorithm for finding a minimum dominating set in a cactus ⋮ The k-limited packing and k-tuple domination problems in strongly chordal, P4-tidy and split graphs ⋮ A parallel algorithm for computing Steiner trees in strongly chordal graphs ⋮ The parallel solution of domination problems on chordal and strongly chordal graphs ⋮ EQUITABLE DOMINATION IN GRAPHS ⋮ Characterizations of two classes of digraphs ⋮ A polyhedral view to a generalization of multiple domination ⋮ On the independent dominating set polytope ⋮ An approximation algorithm for clustering graphs with dominating diametral path ⋮ The weakly connected independent set polytope in corona and join of graphs ⋮ Convexity in Graphs and Hypergraphs ⋮ An improved exact algorithm for the domatic number problem ⋮ Some advances on the set covering polyhedron of circulant matrices ⋮ 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 ⋮ Forbidden submatrices ⋮ Totally balanced and totally unimodular matrices defined by center location problems ⋮ A unified approach to domination problems on interval graphs ⋮ Transversal partitioning in balanced hypergraphs ⋮ Labeling algorithms for domination problems in sun-free chordal graphs ⋮ On dominating set polyhedra of circular interval graphs ⋮ Total domination in block graphs ⋮ Generalized domination and efficient domination in graphs ⋮ The algorithmic use of hypertree structure and maximum neighbourhood orderings ⋮ Roman domination on strongly chordal graphs ⋮ Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs ⋮ Broadcast domination and multipacking in strongly chordal graphs ⋮ Weighted maximum-clique transversal sets of graphs ⋮ On the dominating set polytope ⋮ The multiple domination and limited packing problems in graphs ⋮ On defensive alliances and strong global offensive alliances ⋮ On bondage numbers of graphs: a survey with some comments ⋮ Domination in convex and chordal bipartite graphs ⋮ Domination and total domination on asteroidal triple-free graphs ⋮ Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs ⋮ Independent domination in chordal graphs ⋮ The bottleneck independent domination on the classes of bipartite graphs and block graphs. ⋮ Dominating sets in perfect graphs ⋮ Permutation graphs: Connected domination and Steiner trees ⋮ Algorithmic aspects of clique-transversal and clique-independent sets ⋮ Strongly simplicial vertices of powers of trees ⋮ On total \(f\)-domination: polyhedral and algorithmic results ⋮ Mutual transferability for \((F, B, R)\)-domination on strongly chordal graphs and cactus graphs ⋮ Algorithms for generating strongly chordal graphs ⋮ An optimal algorithm for finding dominating cycles in circular-arc graphs ⋮ On the max min vertex cover problem ⋮ On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size ⋮ Polar SAT and related 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 ⋮ On complexities of minus domination ⋮ The minimum weakly connected independent set problem: polyhedral results and branch-and-cut ⋮ On the \(k\)-limited packing numbers in graphs ⋮ Which claw-free graphs are perfectly orderable? ⋮ A linear algorithm for the group path problem on chordal graphs ⋮ Strong elimination ordering of the total graph of a tree ⋮ Complexity of distance paired-domination problem in graphs ⋮ Shiftable intervals ⋮ The algorithmic complexity of mixed domination in graphs ⋮ Paired-domination problem on distance-hereditary graphs ⋮ The topology of the independence complex ⋮ Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes ⋮ On \(f\)-domination: polyhedral and algorithmic results ⋮ A linear-time algorithm for paired-domination problem in strongly chordal graphs ⋮ On \(P_4\)-transversals of chordal graphs ⋮ On the parameterized complexity of multiple-interval graph problems ⋮ Deferred-query: An efficient approach for some problems on interval graphs ⋮ Linear algorithm for domatic number problem on interval graphs ⋮ \(k\)-tuple domination in graphs ⋮ Graphs with unique dominating sets ⋮ Broadcast Domination in Graphs ⋮ Fractional Dominating Parameters ⋮ Roman Domination in Graphs ⋮ On the computational complexity of upper fractional domination

Cites Work

This page was built for publication: Domination, independent domination, and duality in strongly chordal graphs