Improved approximation algorithms for \(k\)-connected \(m\)-dominating set problems
type: Item
instance of: scholarly article
title: Improved approximation algorithms for \(k\)-connected \(m\)-dominating set problems
zbMATH Open document ID: 1483.68260
author: Zeev Nutov
published in: Information Processing Letters
publication date: 2018-10-19T00:00:00Z
full work available at URL: https://arxiv.org/abs/1703.04230
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 6958572
zbMATH Keywords: \(k\)-connected graph
zbMATH Keywords: \(m\)-dominating set
zbMATH Keywords: approximation algorithm
MaRDI profile type: Publication
OpenAlex ID: W2595035909
arXiv ID: 1703.04230
cites work: Approximation algorithms for highly connected multi-dominating sets in unit disk graphs
cites work: Approximating Fault-Tolerant Domination in General Graphs
cites work: Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
cites work: Improved approximation algorithms for minimum cost node-connectivity augmentation problems
cites work: Approximating minimum-cost connectivity problems via uncrossable bifamilies
cites work: Approximating subset \(k\)-connectivity problems
cites work: An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
cites work: Parameters of Two-Prover-One-Round Game and The Hardness of Connectivity Problems
cites work: Q4860774
cites work: Approximating node connectivity problems via set covers
cites work: Ecken vom Grad \(n\) in minimalen \(n\)-fach zusammenhängenden Graphen
cites work: A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
cites work: Q4878669
cites work: Tight bounds for the vertices of degree k in minimally k‐connected graphs
Wikidata QID: Q129370187
DOI: 10.1016/J.IPL.2018.08.003
description: scientific article