Combinatorial bounds via measure and conquer
From MaRDI portal
Publication:4962767
exact exponential algorithmsmeasure and conquerlisting algorithmsdomatic numberminimum dominating setminimum set cover
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) 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)
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
(48)- Minimal dominating sets in graph classes: combinatorial bounds and enumeration
- Minimal dominating sets in graph classes: combinatorial bounds and enumeration
- Algorithmic aspects of \textsc{Upper Domination}: a parameterised perspective
- On the number of minimum dominating sets and total dominating sets in forests
- Inclusion/exclusion meets measure and conquer
- On the Number of Connected Sets in Bounded Degree Graphs
- Enumerating Minimal Tropical Connected Sets
- Minimal dominating sets in interval graphs and trees
- Proximity Search for Maximal Subgraph Enumeration
- Minimum cost flow problem with conflicts
- Enumeration of minimal connected dominating sets for chordal graphs
- Enumerating minimal connected dominating sets in graphs of bounded chordality
- Feedback vertex sets in tournaments
- Enumeration of maximal irredundant sets for claw-free graphs
- ON THE SECOND DOMINATION HYPER INDEX OF GRAPH AND SOME GRAPH OPERATIONS
- Domination cover number of graphs
- Enumeration and maximum number of maximal irredundant sets for chordal graphs
- Enumeration of maximal irredundant sets for claw-free graphs
- Counting Minimum Weighted Dominating Sets
- Locally definable vertex set properties are efficiently enumerable
- Exact algorithms for dominating set
- Enumeration of minimal dominating sets and variants
- Efficient computation of permanents, with applications to boson sampling and random matrices
- Below all subsets for minimal connected dominating set
- Enumeration of minimal tropical connected sets
- Enumeration and maximum number of minimal dominating sets for chordal graphs
- On the number of minimal separators in graphs
- Computing optimal Steiner trees in polynomial space
- The many facets of upper domination
- Forgotten domination, hyper domination and modified forgotten domination indices of graphs
- Computing the differential of a graph: hardness, approximability and exact algorithms
- Subset feedback vertex sets in chordal graphs
- Maximum matchings and minimum dominating sets in Apollonian networks and extended tower of Hanoi graphs
- On the number of optimal identifying codes in a twin-free graph
- Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph
- Sharp separation and applications to exact and parameterized algorithms
- Algorithms and Computation
- Covering and packing in linear space
- On the number of minimal dominating sets on some graph classes
- Completion and decomposition of hypergraphs into dominating sets of graphs
- Binary programming formulations for the upper domination problem
- Colorings with few colors: counting, enumeration and combinatorial bounds
- Polynomial space algorithms for counting dominating sets and the domatic number
- Colorings with few colors: counting, enumeration and combinatorial bounds
- On the number of connected sets in bounded degree graphs
- Branch and recharge: exact algorithms for generalized domination
- NP-completeness results for partitioning a graph into total dominating sets
- On partitioning a graph into two connected subgraphs
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)
