Computing a tree having a small vertex cover

DOI10.1007/978-3-319-48749-6_6zbMath1430.68203arXiv1701.08897OpenAlexW2945240418WikidataQ127826239 ScholiaQ127826239MaRDI QIDQ2272400

Takuro Fukunaga, Takanori Maehara

Publication date: 10 September 2019

Published in: Theoretical Computer Science, Combinatorial Optimization and Applications (Search for Journal in Brave)

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

zbMATH Keywords

Steiner treeminor-free graphunit disk graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs
• Survivable networks, linear programming relaxations and the parsimonious property
• Lower bound of the Hadwiger number of graphs by their average degree
• Node-weighted Steiner tree approximation in unit disk graphs
• Approximation algorithms for connected dominating sets
• The extremal function for complete minors
• Primal-dual algorithms for connected facility location problems
• Connected facility location via random facility sampling and core detouring
• Approximation algorithms for the connected sensor cover problem
• Approximation Algorithms for Single and Multi-Commodity Connected Facility Location
• A PTAS for the Weighted Unit Disk Cover Problem
• Linear-Time Approximation Algorithms for Unit Disk Graphs
• Min-Power Covering Problems
• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Analytical approach to parallel repetition
• Steiner Tree Approximation via Iterative Randomized Rounding
• Matroids and integrality gaps for hypergraphic steiner tree relaxations
• Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs

This page was built for publication: Computing a tree having a small vertex cover