On connected dominating sets of restricted diameter
From MaRDI portal
Publication:2356248
DOI10.1016/j.ejor.2013.11.036zbMath1317.90303OpenAlexW2071041127MaRDI QIDQ2356248
Austin Buchanan, Je Sang Sung, Sergiy I. Butenko, Vladimir L. Boginski
Publication date: 29 July 2015
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ejor.2013.11.036
Programming involving graphs or networks (90C35) Communication networks in operations research (90B18) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
The maximum independent union of cliques problem: complexity and exact approaches, The Optimal Design of Low-Latency Virtual Backbones, Regenerator location problem: polyhedral study and effective branch-and-cut algorithms, Distance-Based Clique Relaxations in Networks: s-Clique and s-Club, A matheuristic approach for solving the 2-connected dominating set problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems
- An exact algorithm for the maximum leaf spanning tree problem
- Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
- Solving connected dominating set faster than \(2^n\)
- Reformulations and solution algorithms for the maximum leaf spanning tree problem
- Complete description of forbidden subgraphs in the structural domination problem
- On domination problems for permutation and other graphs
- Dominating cliques in \(P_ 5\)-free graphs
- The complexity of domination problems in circle graphs
- Approximation algorithms for connected dominating sets
- An exact algorithm for the maximum leaf spanning tree problem.
- An exact algorithm for the maximum \(k\)-club problem in an undirected graph
- On clique relaxation models in network analysis
- On dominating sets whose induced subgraphs have a bounded diameter
- An exact algorithm for the minimum dominating clique problem
- Novel approaches for analyzing biological networks
- Algorithmic construction of sets for k -restrictions
- The Minimum Connected Dominating Set Problem: Formulation, Valid Inequalities and a Branch-and-Cut Algorithm
- Solving the Connected Dominating Set Problem and Power Dominating Set Problem by Integer Programming
- Hereditary Domination in Graphs: Characterization with Forbidden Induced Subgraphs
- Polynomial-time data reduction for dominating set
- Approximating Maximum Leaf Spanning Trees in Almost Linear Time
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
- The maximum-leaf spanning tree problem: Formulations and facets
- Dominating cliques in graphs
