Lower bounds for combinatorial problems on graphs |
| |
Authors: | Hiroyuki Nakayama Takao Nishizeki Nobuji Saito |
| |
Affiliation: | Kyoto Works of Mitsubishi Electric Corp., Nagaokakyo, 617 Japan;Department of Electrical Communications, Faculty of Engineering, Tohoku University, Sendai 980, Japan |
| |
Abstract: | Nontrivial lower bounds are given for the computation time of various combinatorial problems on graphs under a linear or algebraic decision tree model. An bound is obtained for a “travelling salesman problem” on a weighted complete graph of n vertices. Moreover it is shown that the same bound is valid for the “subgraph detection problem” with respect to property P if P is hereditary and determined by components. Thus an bound is established in a unified way for a rather large class of problems. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|