Polynomial testing of the query “IS ab ≥ cd?” with application to finding a minimal cost reliability ratio spanning tree |
| |
| Authors: | R Chandrasekaran A Tamir |
| |
| Institution: | University of Texas at Dallas, P.O. Box 688, Richardson, TX 75080, USA;Statistics Department, Tel Aviv University, Tel Aviv 69978, Israel |
| |
| Abstract: | Given integers a, b, c, d, we present a polynomial algorithm for the query “is ab ≥ cd?”. The result is applied to yield a polynomial algorithm for the minimal cost reliability ratio spanning tree problem. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
