Cited By
View all- Krysta P(2003)Approximating minimum size {1,2}-connected networksDiscrete Applied Mathematics10.1016/S0166-218X(02)00199-3125:2-3(267-288)Online publication date: 1-Feb-2003
Approximating multiroot 3-outconnected subgraphs
Author: 
Zeev NutovAuthors Info & Claims
Zeev NutovAuthors Info & ClaimsAbstract
No abstract available.
References
[1]
J. Cheriyau, T. Jord#u, & Z. Nutov, Approximating k. outconnected subgraph problems, Approximation Algorithms for Combinatorial Optimization, Springer Lectuxe Notes in Computer Science 1444 (1998), pp. 77-88.
[2]
A. Frank & }#. Taxdos, An application of submodular flows, Linear Algebra and its Applications, 114/115 (1989), pp. 329--348.
[3]
S. KhuUer &= B. Raghavachaxi: improved approxima- $ion algorithms for uniform connectivity problems, J. of Algorithms, 21 (I996), pp. 434--450.
[4]
Z. Nutov, Approximating multiroot 3-outconnected subgraphs, ma#auscript, available at http://www.mpisb.mpg.de/- nutov/
[5]
Z. N utov, M. Penn, & D. Sinreid#, On mobile robots flow in locally uniform networks, Can. J. of Information Systems and Operational Research Vol. 35, No. 4 (1997), pp. 197-208.
[6]
R. Ravi &: D. P. Williamson: An approximation at9o. rithm for minimum.cost reflex-connectivity problems, Algorithmica, 18 (1997), pp. 21-43.
Index Terms
- Approximating multiroot 3-outconnected subgraphs
Recommendations
Approximating Maximum Subgraphs without Short Cycles
We study approximation algorithms, integrality gaps, and hardness of approximation of two problems related to cycles of “small” length $k$ in a given (undirected) graph. The instance for these problems consists of a graph $G=(V,E)$ and an integer $k$. ...
Approximating k-node Connected Subgraphs via Critical Graphs
We present two new approximation algorithms for the problem of finding a k-node connected spanning subgraph (directed or undirected) of minimum cost. The best known approximation guarantees for this problem were $O(\min \{k,\frac{n}{\sqrt{n-k}}\})$ for ...
Comments
Information & Contributors
Information
Published In
Sponsors
- SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
- SIAM: Society for Industrial and Applied Mathematics
Publisher
Society for Industrial and Applied Mathematics
United States
Publication History
Published: 01 January 1999
Check for updates
Qualifiers
- Article
Conference
SODA99
Sponsor:
- SIGACT
- SIAM
Acceptance Rates
Overall Acceptance Rate 411 of 1,322 submissions, 31%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 24Total Downloads
- Downloads (Last 12 months)9
- Downloads (Last 6 weeks)4
Reflects downloads up to 15 Sep 2024
Other Metrics
Citations
Cited By
View all- Krysta P(2003)Approximating minimum size {1,2}-connected networksDiscrete Applied Mathematics10.1016/S0166-218X(02)00199-3125:2-3(267-288)Online publication date: 1-Feb-2003
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in