Augmenting undirected node-connectivity by one
Association for Computing Machinery
(2010-06-06 - 2010-06-08)
Augmenting undirected node-connectivity by one
[Paper]. STOC 2010 - 42nd ACM Symposium on Theory of Computing, Cambridge, United States, USA.
https://doi.org/10.1145/1806689.1806767
We present a min-max formula for the problem of augmenting the node-connectivity of a graph by one and give a polynomial time algorithm for finding an optimal solution. We also solve the minimum cost version for node-induced cost functions.
| Item Type | Conference or Workshop Item (Paper) |
|---|---|
| Copyright holders | © 2010 ACM |
| Departments | LSE > Academic Departments > Management |
| DOI | 10.1145/1806689.1806767 |
| Date Deposited | 11 Oct 2012 |
| URI | https://researchonline.lse.ac.uk/id/eprint/45892 |
Explore Further
- http://www.lse.ac.uk/Mathematics/people/Laszlo-Vegh.aspx (Author)
- https://www.scopus.com/pages/publications/77954716608 (Scopus publication)
- http://research.microsoft.com/en-us/um/newengland/... (Official URL)