ISSN:
1432-0541
Keywords:
Circuits
;
Probabilistic circuits
;
Poly-log depth
;
Parametric problems
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01553905
Permalink