Premium
Approximation algorithms for finding low‐degree subgraphs
Author(s) -
Klein Philip N.,
Krishnan Radha,
Raghavachari Balaji,
Ravi R.
Publication year - 2004
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20031
Subject(s) - degree (music) , combinatorics , mathematics , spanning tree , vertex connectivity , minimum spanning tree , graph , discrete mathematics , approximation algorithm , enhanced data rates for gsm evolution , algorithm , computer science , vertex (graph theory) , telecommunications , physics , acoustics
We give quasipolynomial‐time approximation algorithms for designing networks with a minimum degree. Using our methods, one can design networks whose connectivity is specified by “proper” functions, a class of 0–1 functions indicating the number of edges crossing each cut. We also provide quasipolynomial‐time approximation algorithms for finding two‐edge‐connected spanning subgraphs of approximately minimum degree of a given two‐edge‐connected graph, and a spanning tree (branching) of approximately minimum degree of a directed graph. The degree of the output network in all cases is guaranteed to be at most (1 + ϵ) times the optimal degree, plus an additive O (log 1+ϵ n ) for any ϵ > 0. Our analysis indicates that the degree of an optimal subgraph for each of the problems above is well estimated by certain polynomially solvable linear programs. This suggests that the linear programs we describe could be useful in obtaining optimal solutions via branch and bound. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(3), 203–215 2004