Extending NC and RNC algorithms |
| |
Authors: | Nimrod Megiddo |
| |
Affiliation: | 1. IBM Almaden Research Center, 650 Harry Road, 95120-6099, San Jose, CA, USA 2. School of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel
|
| |
Abstract: | A technique is presented by which NC and RNC algorithms for some problems can be extended into NC and RNC algorithms, respectively, that solve more general parametric problems. The technique is demonstrated on explicit bounded degree circuits. Applications include parametric extensions of the shortest-path and spanning-tree problems and, in particular, the minimum-ratio-cycle problem, showing all these problems are in NC. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|