Space efficient algorithms for some graph theoretical problems
Tóm tắt
We present space-efficient-O(log2
n)-deterministic algorithms for some graph theoretical problems such as planarity testing, producing a plane embedding, finding minimum cost spanning trees, obtaining the connected, biconnected and triconnected components of a graph. Previous planarity algorithms used Ω(n) space. Several algorithms are based on a space-efficient matrix inversion method. The same bounds hold for uniform circuit depth.
Tài liệu tham khảo
Aho, A., Hopcroft, J.E., Ullman, J.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA (1974)
Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. American Elsevier, NY (1977)
Borodin, A., Cook, S., Pippinger, N.: personal communication
Chandra, A.K., Stockmeyer, L.: Alternation. Proc. 17th Ann. FOCS Symp. 98–108 (1976)
Cook, S.: An Observation on Time-Storage Tradeoff. JCSS 9, 308–316 (1974)
Csanky, L.: Fast Parallel Matrix Inversion Algorithms. SIAM J. COMP. 5, 618–623 (1976)
Harary, F.: Graph Theory. Addison-Wesley, Reading, MA (1969)
Hartmanis, J., Simon, J.: On the Power of Multiplication in Random Access Machines. Proc. 15th SWAT Symp. 13–23 (1974)
Heller, D.: A Determinant Theorem with Applications to Parallel Algorithms. Tech. Rept., Dept. Comp. Sci., Carnegie-Mellon University (March 1973)
Ja'Ja', J., Simon, J.: Some Space-Efficient Algorithms. Proc. 17th Allerton Conference 677–684 (1979)
Ja'Ja', J., Simon, J.: Parallel Algorithms in Graph Theory: Planarity Testing. CS-80-14, Computer Science Department, The Pennsylvania State University, June 1980
Lewis, P.M., Stearns, R.E., Hartmanis, J.: Memory Bounds for Recognition of Context-Free and Context-Sensitive Languages. IEEE Conf. Rec. Switch. Th., Ann Arbor, Mich. 191–202 (1951)
McLane, S.: A Structural Characterization of Planar Combinatorial Graphs. Duke Math. J. 3, 460–472 (1937)
Paul, W.J., Rudiger, R.: On Space vs. Time II. Proc. 20th FOCS Conf. (1979)
Savage, C., Ja'Ja', J.: Fast, Efficient Parallel Algorithms for Some Graph Problems. submitted for publication
Savitch, W.: Relationships Between Nondeterministic and Deterministic Space Complexities. JCSS 4, 177–192 (1970)
Simon, J.: On Tape Bounded Probabilistic Turing Machine Acceptors. To appear in TCS
Tutte, W.: How to Draw a Graph. Proc. London Math. Soc. B13, 743–768 (1963)