๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Lower bounds on time complexity for some subgraph detection problems

โœ Scribed by Masanari Arai; Masafumi Yamashita; Tomio Hirata; Toshihide Ibaraki; Namio Honda

Book ID
112205542
Publisher
John Wiley and Sons
Year
1986
Tongue
English
Weight
513 KB
Volume
17
Category
Article
ISSN
0882-1666

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

A lower time bound for the knapsack prob
A lower time bound for the knapsack problem on random access machines
โœ Peter Klein; Friedhelm Meyer Heide ๐Ÿ“‚ Article ๐Ÿ“… 1983 ๐Ÿ› Springer-Verlag ๐ŸŒ English โš– 533 KB

a.M. (Fed. Rep.) Summary. We consider random access machines which read the input integer by integer (not bit by bit). For this computational model we prove a quadratic lower bound for the n-dimensional knapsack problem. For this purpose, we combine a method due to Paul and Simon [1] to apply decisi