On the Aanderaa-Rosenberg Conjecture
- 1 January 1974
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGACT News
- Vol. 6 (1) , 30-31
- https://doi.org/10.1145/1811129.1811133
Abstract
In a recent paper [1], Rosenberg conjectures that the results found in Holt and Reingold [2], can be generalized. Suppose that graphs are presented via their adjacency matrices. Then Holt and Reingold show that any algorithm which detects whether or not a graph is strongly connected (respectively, contains a cycle) must in worst case probe 0(n 2 ) entries of the given n x n adjacency matrix. Rosenberg then considers restrictions on graph property P such that any algorithm takes in worst case 0(n 2 ) probes to determine whether or not a n-node graph has property P.Keywords
This publication has 2 references indexed in Scilit:
- On the time required to recognize properties of graphsACM SIGACT News, 1973
- On the time required to detect cycles and connectivity in graphsTheory of Computing Systems, 1972