Domination, independent domination, and duality in strongly chordal graphs
From MaRDI portal
Publication:788002
DOI10.1016/0166-218X(84)90061-1zbMATH Open0531.05045OpenAlexW2050228489WikidataQ127740357 ScholiaQ127740357MaRDI QIDQ788002FDOQ788002
Authors: Martin Farber 
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
Recommendations
- Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
- scientific article; zbMATH DE number 4045183
- Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
- Steiner trees, connected domination and strongly chordal graphs
- A simple linear time algorithm for the domatic partition problem on strongly chordal graphs
strongly chordal graphsindependent dominating setstotally balanced matricesminimum weight dominating sets
Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Characterizations of strongly chordal graphs
- Triangulated graphs and the elimination process
- Characterizations of totally balanced matrices
- Towards a theory of domination in graphs
- Title not available (Why is that?)
- Algorithmic Aspects of Vertex Elimination on Graphs
- A linear algorithm for the domination number of a tree
- Totally-Balanced and Greedy Matrices
- The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
- Title not available (Why is that?)
- Dominating Sets in Chordal Graphs
- Title not available (Why is that?)
- Balanced matrices
- Independent domination in chordal graphs
- Title not available (Why is that?)
- Optimum domination in weighted trees
- R -Domination in Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (only showing first 100 items - show all)
- Algorithmic aspects of clique-transversal and clique-independent sets
- The bottleneck independent domination on the classes of bipartite graphs and block graphs.
- Dominating cliques in chordal graphs
- A linear algorithm for the group path problem on chordal graphs
- A polyhedral view to a generalization of multiple domination
- The \(k\)-limited packing and \(k\)-tuple domination problems in strongly chordal, \(P_{4}\)-tidy and split graphs
- Permutation graphs: Connected domination and Steiner trees
- A linear-time algorithm for paired-domination problem in strongly chordal graphs
- The domatic number of block-cactus graphs
- An improved exact algorithm for the domatic number problem
- Weighted maximum-clique transversal sets of graphs
- Labeling algorithms for domination problems in sun-free chordal graphs
- Independent domination in chordal graphs
- Location problems
- The domatic number problem on some perfect graph families
- Deferred-query—An efficient approach for problems on interval and circular-arc graphs
- It is all labeling
- Total domination in block graphs
- Dually and strongly chordal graphs
- Roman domination on strongly chordal graphs
- The topology of the independence complex
- On the \(k\)-limited packing numbers in graphs
- Generalized domination and efficient domination in graphs
- On total \(f\)-domination: polyhedral and algorithmic results
- 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
- A characterization of strongly chordal graphs
- An approximation algorithm for clustering graphs with dominating diametral path
- Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs
- Independent Domination in Triangle Graphs
- On the computational complexity of upper fractional domination
- Title not available (Why is that?)
- Deferred-query: An efficient approach for some problems on interval graphs
- Characterizations of strongly chordal graphs
- The algorithmic complexity of mixed domination in graphs
- Fractional domination of strong direct products
- Complexity of distance paired-domination problem in graphs
- On \(f\)-domination: polyhedral and algorithmic results
- Domination in convex and chordal bipartite graphs
- Broadcast domination in graphs
- Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
- The domatic number problem
- The algorithmic use of hypertree structure and maximum neighbourhood orderings
- Construction of a simple elimination scheme for a chordal comparability graph in linear time
- Dominating sets in perfect graphs
- On the parameterized complexity of multiple-interval graph problems
- \(k\)-tuple domination in graphs
- A linear algorithm for finding a minimum dominating set in a cactus
- Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
- Recognizing clique graphs of directed and rooted path graphs
- Dominating sets and domatic number of circular arc graphs
- On bondage numbers of graphs: a survey with some comments
- Totally balanced and totally unimodular matrices defined by center location problems
- Real and integer domination in graphs
- Fractional domination game
- Domination and total domination on asteroidal triple-free graphs
- Independent domination in hereditary classes
- Packing and domination parameters in digraphs
- On the algorithmic complexity of twelve covering and independence parameters of graphs
- Which claw-free graphs are perfectly orderable?
- The bondage and reinforcement numbers of \(\gamma_ f\) for some graphs
- A simple linear time algorithm for the domatic partition problem on strongly chordal graphs
- Linear algorithm for domatic number problem on interval graphs
- On the Algorithmic Complexity of Total Domination
- Convexity in Graphs and Hypergraphs
- On the max min vertex cover problem
- On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
- Total domination in interval graphs
- A linear‐time algorithm for broadcast domination in a tree
- On the dominating set polytope
- A unified approach to domination problems on interval graphs
- Some advances on the set covering polyhedron of circulant matrices
- The multiple domination and limited packing problems in graphs
- Roman domination in graphs
- \(r\)-dominating cliques in graphs with hypertree structure
- On \(P_4\)-transversals of chordal graphs
- An optimal algorithm for finding dominating cycles in circular-arc graphs
- Forbidden submatrices
- On defensive alliances and strong global offensive alliances
- Broadcast domination and multipacking in strongly chordal graphs
- Efficient \((j, k)\)-dominating functions
- CONVEXITY OF MINIMAL DOMINATING FUNCTIONS OF TREES: A SURVEY
- Extension and its price for the connected vertex cover problem
- Weighted connected domination and Steiner trees in distance-hereditary graphs
- Paired-domination problem on distance-hereditary graphs
- The weakly connected independent set polytope in corona and join of graphs
- On complexities of minus domination
- Strong elimination ordering of the total graph of a tree
- The minimum weakly connected independent set problem: polyhedral results and branch-and-cut
- Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs
- Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms
- Polar SAT and related graphs
- Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs
- Title not available (Why is that?)
- Fractional dominating parameters
- Algorithms for generating strongly chordal graphs
- On the independent dominating set polytope
- On dominating set polyhedra of circular interval graphs
- The algorithmic use of hypertree structure and maximum neighbourhood orderings
- Weighted upper edge cover: complexity and approximability
This page was built for publication: Domination, independent domination, and duality in strongly chordal graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q788002)
