Linear separation of connected dominating sets in graphs
DOI10.26493/1855-3974.1330.916zbMath1416.05207arXiv1610.06539OpenAlexW2395657177MaRDI QIDQ5225055
Martin Milanič, Nina Chiarelli
Publication date: 25 July 2019
Published in: Ars Mathematica Contemporanea (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1610.06539
split graphpolynomial-time algorithmchordal graphconnected dominating setminimal cutsetminimal separatorforbidden induced subgraph characterizationconnected dominationthreshold Boolean functionthreshold hypergraph1-Sperner hypergraphconnected-domishold graph
Hypergraphs (05C65) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40)
Related Items (3)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On graphs for which the connected domination number is at most the total domination number
- A note on connected dominating sets of distance-hereditary graphs
- Connected dominating set. Theory and applications
- Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs
- On connected domination in unit ball graphs
- Complexity results for equistable graphs and related classes
- A new polynomial-time algorithm for linear programming
- On rigid circuit graphs
- A class of threshold and domishold graphs: Equistable and equidominating graphs
- A linear time algorithm to list the minimal separators of chordal graphs
- Hereditarily dominated graphs
- Efficient algorithms for the minimum connected domination on trapezoid graphs
- Computational aspects of monotone dualization: a brief survey
- Solving connected dominating set faster than \(2^n\)
- Connected domination of regular graphs
- Threshold hypergraphs
- Dualization of regular Boolean functions
- Polynomial-time algorithms for regular set-covering and threshold synthesis
- An O(m n) algorithm for regular set-covering problems
- The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
- The complexity of domination problems in circle graphs
- Trivially perfect graphs
- Weighted connected domination and Steiner trees in distance-hereditary graphs
- Minimal vertex separators of chordal graphs
- An \(O(nm)\)-time algorithm for computing the dual of a regular Boolean function
- Weighted domination of cocomparability graphs
- Efficient enumeration of all minimal separators in a graph
- Hereditary dominating pair graphs
- Algorithmic graph theory and perfect graphs
- Threshold graphs and related topics
- Quasi-threshold graphs
- The complexity of connected dominating sets and total dominating sets with specified induced subgraphs
- A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph
- Threshold graphs, shifted complexes, and graphical complexes
- Treewidth and Minimum Fill-in: Grouping the Minimal Separators
- Linear Separation of Total Dominating Sets in Graphs
- Rainbow connection number and connected dominating sets
- On Distance-d Independent Set and Other Problems in Graphs with “few” Minimal Separators
- Algorithmic Aspects of Vertex Elimination on Graphs
- Linear Separation of Dominating Sets in Graphs
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- Graph Classes: A Survey
- Listing all Minimal Separators of a Graph
- Hamilton cycles in split graphs with large minimum degree
- On the Recognition of k-Equistable Graphs
- On the Enumeration of Minimal Dominating Sets and Related Notions
- GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
- Analytical approach to parallel repetition
- A dominating-set-based routing scheme in ad hoc wireless networks
This page was built for publication: Linear separation of connected dominating sets in graphs
