(This list is still being updated.)

• Region-Fault Toerant Geometric Spanners
  M. A. Abam, M. de Berg, M. Farshi, F. Gudmundsson
  SODA 2007
  This paper assumes complete graph in a geometric space. It's related, but the particular technique might not be applicable.

• Relay placement for higher order connectivity in sensor networks
  A. Kashyap, S. Khuller and M. Shayman
  Infocom 2006

• Approximation Schemes for Minimum-Cost k-Connectivity Problems in Geometric Graphs
  Artur Czumaj and Andrzej Lingas

• FLSS: a fault-tolerant topology control algorithm for wireless networks
  Ning Li, Jennifer C. Hou
  Mobicom 2004

• Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks
  MohammadTaghi Hajiaghayi, Nicole Immorlica, Vahab S. Mirrokni
  Mobicom 2003

• Approximating Minimum-size k-Connected Spanning Subgraphs via Matching
  Joseph Cheriyan, Ramakrishna Thurimella
  SIAM J of Computing Vol 30 No 2 pp 528--560, 2000

• Sub-Linear Distributed Algorithms for Sparse Certificates and Biconnected Components
  Ramakrishna Thurimella
  J. of Algorithm 97 (earlier version in PODC 95)

• Improved approximation algorithms for uniform connectivity problems
  S. Khuller, B. Raghavachari
  J. Albegra, 21 (1996) pp 434--450
  There is an algorithm for vertex bi-connectivity, which utilizes a k-outconnectivity problem by Frank and Tardos. In our case, two paths need to be "set"-disjoint, not vertex-disjoint alone. It is not immediately clear how to apply this, but might be useful if we can find multiple set-disoint paths (and thus outconnected subgraphs).

• Distributed algorithms for sparse k-connectivity certificates
  Esther Jennings and Lenka Motyckova
  PODC 96

Keywords that might be relevant
• articulation set

Home