Combinatorial bounds via measure and conquer

DOI10.1145/1435375.1435384zbMath1445.05101OpenAlexW2085870956WikidataQ60488725 ScholiaQ60488725MaRDI QIDQ4962767

Alexey A. Stepanov, Fedor V. Fomin, Fabrizio Grandoni, Artem V. Pyatkin

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1435375.1435384

zbMATH Keywords

exact exponential algorithms listing algorithms measure and conquer domatic number minimum dominating set minimum set cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (45)

Forgotten domination, hyper domination and modified forgotten domination indices of graphs ⋮ Enumerating minimal connected dominating sets in graphs of bounded chordality ⋮ Enumeration of Maximal Irredundant Sets for Claw-Free Graphs ⋮ Minimal Dominating Sets in Graph Classes: Combinatorial Bounds and Enumeration ⋮ On the number of connected sets in bounded degree graphs ⋮ Efficient computation of permanents, with applications to boson sampling and random matrices ⋮ Enumeration of maximal irredundant sets for claw-free graphs ⋮ Proximity Search for Maximal Subgraph Enumeration ⋮ Completion and decomposition of hypergraphs into dominating sets of graphs ⋮ Colorings with few colors: counting, enumeration and combinatorial bounds ⋮ Computing optimal Steiner trees in polynomial space ⋮ Minimal dominating sets in interval graphs and trees ⋮ Enumeration of minimal connected dominating sets for chordal graphs ⋮ Maximum matchings and minimum dominating sets in Apollonian networks and extended tower of Hanoi graphs ⋮ Minimal dominating sets in graph classes: combinatorial bounds and enumeration ⋮ On the Number of Connected Sets in Bounded Degree Graphs ⋮ Enumeration of minimal tropical connected sets ⋮ Minimum cost flow problem with conflicts ⋮ Binary programming formulations for the upper domination problem ⋮ Exact algorithms for dominating set ⋮ ON THE SECOND DOMINATION HYPER INDEX OF GRAPH AND SOME GRAPH OPERATIONS ⋮ Covering and packing in linear space ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ The many facets of upper domination ⋮ Enumerating Minimal Tropical Connected Sets ⋮ Feedback Vertex Sets in Tournaments ⋮ Branch and recharge: exact algorithms for generalized domination ⋮ On partitioning a graph into two connected subgraphs ⋮ Subset feedback vertex sets in chordal graphs ⋮ Computing the differential of a graph: hardness, approximability and exact algorithms ⋮ On the number of optimal identifying codes in a twin-free graph ⋮ On the number of minimal dominating sets on some graph classes ⋮ Domination cover number of graphs ⋮ Locally definable vertex set properties are efficiently enumerable ⋮ Complexity of Grundy coloring and its variants ⋮ Inclusion/exclusion meets measure and conquer ⋮ Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph ⋮ Below All Subsets for Minimal Connected Dominating Set ⋮ Colorings with Few Colors: Counting, Enumeration and Combinatorial Bounds ⋮ Enumeration and maximum number of maximal irredundant sets for chordal graphs ⋮ NP-completeness results for partitioning a graph into total dominating sets ⋮ Enumeration of Minimal Dominating Sets and Variants ⋮ On the Number of Minimal Separators in Graphs ⋮ Algorithmic Aspects of Upper Domination: A Parameterised Perspective ⋮ Enumeration and maximum number of minimal dominating sets for chordal graphs

This page was built for publication: Combinatorial bounds via measure and conquer