Combinatorial bounds via measure and conquer

DOI10.1145/1435375.1435384zbMath1445.05101WikidataQ60488725 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

68Q25: Analysis of algorithms and problem complexity

68W40: Analysis of algorithms

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Domination cover number of graphs, Below All Subsets for Minimal Connected Dominating Set, Feedback Vertex Sets in Tournaments, Forgotten domination, hyper domination and modified forgotten domination indices of graphs, Proximity Search for Maximal Subgraph Enumeration, Enumeration of Maximal Irredundant Sets for Claw-Free Graphs, 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 tropical connected sets, Binary programming formulations for the upper domination problem, ON THE SECOND DOMINATION HYPER INDEX OF GRAPH AND SOME GRAPH OPERATIONS, Enumerating minimal connected dominating sets in graphs of bounded chordality, Completion and decomposition of hypergraphs into dominating sets of graphs, Minimal dominating sets in interval graphs and trees, Minimal dominating sets in graph classes: combinatorial bounds and enumeration, Exact algorithms for 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, Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph, Branch and recharge: exact algorithms for generalized domination, On partitioning a graph into two connected subgraphs, 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, Complexity of Grundy coloring and its variants, 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, On the Number of Minimal Separators in Graphs, Algorithmic Aspects of 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