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)
- 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
- Graphs with unique dominating sets
- Linear programming approach for various domination parameters
- Broadcast domination and multipacking: bounds and the integrality gap
- Equitable domination in graphs
- Strongly simplicial vertices of powers of trees
- Independent domination in directed graphs
- Strong Cocomparability Graphs and Slash-Free Orderings of Matrices
- Characterizations of two classes of digraphs
- On complexities of minus domination
- A parallel algorithm for computing Steiner trees in strongly chordal graphs
- Semipaired Domination in Some Subclasses of Chordal Graphs
- A tight relation between series-parallel graphs and bipartite distance hereditary graphs
- Common extremal graphs for three inequalities involving domination parameters
- A linear-time algorithm for semitotal domination in strongly chordal graphs
- Shiftable intervals
- An optimal parallel algorithm for the domatic partition problem on an interval graph given its sorted model
- Polynomial reductions between the limited packing and tuple domination problems in graphs
- The parallel solution of domination problems on chordal and strongly chordal graphs
- One-node cutsets and the dominating set polytope
- Approximation hardness of domination problems on generalized convex graphs
- EXTREMUM AGGREGATES OF MINIMAL 0-DOMINATING FUNCTIONS OF GRAPHS
- Mobility offer allocations in corporate settings
- Transversal partitioning in balanced hypergraphs
- Strong Chordality of Graphs with Possible Loops
- Semi-dynamic algorithms for strongly chordal graphs
- 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
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)
