Abstract
We show that minimal k-vertex connected spanning subgraphs of a given graph can be generated in incremental polynomial time for any fixed k.
- Title
- Generating Minimal k-Vertex Connected Spanning Subgraphs
- Creators
- Endre Boros - RUTCOR, Rutgers University, 640 Bartholomew Road, Piscataway NJ 08854-8003,Konrad Borys - RUTCOR, Rutgers University, 640 Bartholomew Road, Piscataway NJ 08854-8003,Khaled Elbassioni - Max-Planck-Institut für Informatik, Saarbrücken, GermanyVladimir Gurvich - RUTCOR, Rutgers University, 640 Bartholomew Road, Piscataway NJ 08854-8003,Kazuhisa Makino - Division of Mathematical Science for Social Systems, Graduate School of Engineering Science, Osaka University, Toyonaka, Osaka, 560-8531, JapanGabor Rudolf - RUTCOR, Rutgers University, 640 Bartholomew Road, Piscataway NJ 08854-8003,
- Publication Details
- Computing and Combinatorics, pp.222-231
- Date published
- 2007
- Series
- Lecture Notes in Computer Science
- Publisher
- Springer Berlin Heidelberg; Berlin, Heidelberg
- Academic Unit
- Management Science and Information Systems (RBS)
- Language
- English
- Resource Type
- Book chapter
- Identifiers
- 991031665928404646