Average-case complexity of a branch-and-bound algorithm for \textsc{Min Dominating Set}

DOI10.1016/J.DAM.2023.11.021MaRDI QIDQ6145803zbMATH OpenOpenAlexFDO

Authors Tom Denat, Ararat Harutyunyan, Nikolaos Melissinos, Vangelis Th. Paschos

Publication date 9 January 2024

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1902.01874

zbMATH Keywords

approximation schemecombinatorial optimizationknapsack problemssubset-sums ratio

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Abstract: The average-case complexity of a branch-and-bound algorithms for Minimum Dominating Set problem in random graphs in the G(n,p) model is studied. We identify phase transitions between subexponential and exponential average-case complexities, depending on the growth of the probability p with respect to the number n of nodes.

Recommendations

• Near-optimal dominating sets in dense random graphs in polynomial expected time
• Minimum connected dominating sets in finite graphs
• A note on the complexity of minimum dominating set
• Graph-Theoretic Concepts in Computer Science
• The average order of dominating sets of a graph

Cites work

• Analysis of an Exhaustive Search Algorithm in Random Graphs and the $n^{c\log n}$-Asymptotics
• Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs
• Branch-and-bound solves random binary IPs in poly(n)-time
• Exact algorithms for dominating set
• Exact algorithms for maximum independent set
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 3303655 (Why is no real title available?)
• On the integrality gap of binary integer programs with Gaussian data
• Progress in computational mixed integer programming -- a look back from the other side of the tipping point

This page was built for publication: Average-case complexity of a branch-and-bound algorithm for \textsc{Min Dominating Set}

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6145803)