Graph-theoretic properties in computational complexity
作者：
Highlights：
•
摘要
The extent to which a set of related graph-theoretic properties can be used to accont for the superlinear complexity of computational problems is explored. While a previously widely held positive conjecture is refuted, it is also shown that certain limited lower bounds can be proved by means of such properties.
论文关键词：
论文评审过程：Received 23 September 1975, Revised 30 January 1976, Available online 27 December 2007.
论文官网地址：https://doi.org/10.1016/S0022-0000(76)80041-4
