Combinatorial bounds via measure and conquer
From MaRDI portal
Publication:4962767
domatic numberexact exponential algorithmslisting algorithmsmeasure and conquerminimum dominating setminimum set cover
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)
Recommendations
- Algorithms and Computation
- Bounds on the maximum number of minimum dominating sets
- Minimal dominating sets in graph classes: combinatorial bounds and enumeration
- Minimal dominating sets in graph classes: combinatorial bounds and enumeration
- The computational complexity of dominating set problems for instances with bounded minors of constraint matrices
- Minimum dominating set approximation in graphs of bounded arboricity
- On the enumeration of minimal dominating sets and related notions
- On approximating the minimum independent dominating set
- A note on the complexity of minimum dominating set
- Majorization and the minimum number of dominating sets
Cited in
(55)- On the number of connected sets in bounded degree graphs
- Enumeration of maximal irredundant sets for claw-free graphs
- Maximum matchings and minimum dominating sets in Apollonian networks and extended tower of Hanoi graphs
- The many facets of upper domination
- Covering and packing in linear space
- Locally definable vertex set properties are efficiently enumerable
- Efficient computation of permanents, with applications to boson sampling and random matrices
- Enumeration of minimal connected dominating sets for chordal graphs
- Inclusion/exclusion meets measure and conquer
- Enumeration and maximum number of minimal dominating sets for chordal graphs
- Colorings with few colors: counting, enumeration and combinatorial bounds
- Computing optimal Steiner trees in polynomial space
- Sharp separation and applications to exact and parameterized algorithms
- Subset feedback vertex sets in chordal graphs
- Computing the differential of a graph: hardness, approximability and exact algorithms
- Enumerating minimal connected dominating sets in graphs of bounded chordality
- On the number of minimal separators in graphs
- Algorithmic aspects of \textsc{Upper Domination}: a parameterised perspective
- Minimal dominating sets in graph classes: combinatorial bounds and enumeration
- On the Number of Connected Sets in Bounded Degree Graphs
- Enumerating Minimal Tropical Connected Sets
- Colorings with few colors: counting, enumeration and combinatorial bounds
- Enumeration of minimal dominating sets and variants
- Completion and decomposition of hypergraphs into dominating sets of graphs
- Minimal dominating sets in interval graphs and trees
- Polynomial space algorithms for counting dominating sets and the domatic number
- Counting Minimum Weighted Dominating Sets
- Minimal dominating sets in graph classes: combinatorial bounds and enumeration
- Exact algorithms for dominating set
- Domination cover number of graphs
- Below all subsets for minimal connected dominating set
- On the number of optimal identifying codes in a twin-free graph
- On the number of minimal dominating sets on some graph classes
- Feedback vertex sets in tournaments
- Forgotten domination, hyper domination and modified forgotten domination indices of graphs
- Proximity Search for Maximal Subgraph Enumeration
- Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph
- Enumeration of maximal irredundant sets for claw-free graphs
- Algorithms and Computation
- NP-completeness results for partitioning a graph into total dominating sets
- Enumeration and maximum number of maximal irredundant sets for chordal graphs
- Enumeration of minimal tropical connected sets
- Minimum cost flow problem with conflicts
- Binary programming formulations for the upper domination problem
- ON THE SECOND DOMINATION HYPER INDEX OF GRAPH AND SOME GRAPH OPERATIONS
- Branch and recharge: exact algorithms for generalized domination
- On partitioning a graph into two connected subgraphs
- On the number of minimum dominating sets and total dominating sets in forests
- Enumerating minimal defensive alliances
- Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets
- Quantum algorithms for graph coloring and other partitioning, covering, and packing problems
- Enumerating minimal connected dominating sets
- Enumerating minimal connected dominating sets
- Parameterized complexity of paired domination
- Roman census: enumerating and counting Roman dominating functions on graph classes
This page was built for publication: Combinatorial bounds via measure and conquer
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4962767)
