×

Algorithms for weighted graph problems on the modified cellular graph automaton. (English) Zbl 0678.68063

Summary: A modified cellular graph automaton (MCGA) is formulated and algorithms for solving weighted graph problems viz., minimum weight spanning tree construction (based on Kruskal’s sequential algorithm [A. V. Aho, J. E. Hopcroft, J. D. Ullman; The design and analysis of computer algorithms. (Addison Wesley, 1974; Zbl 0326.68005)]) and single source shortest paths (based on Dijkstra’s sequential algorithm [N. Deo; Graph theory with applications to engineering and computer science. (Prentice-Hall, 1974; Zbl 0285.05102)]) are described on it. The original cellular graph automaton (CGA) of A. Wu and A. Rosenfeld [Inf. Control. 42, 305-329 and ibid. 330-353 (1979; Zbl 0424.68029 and Zbl 0424.68030)] is modified by the introduction of a second type of finite state automaton (FSA) on the edges of the input d-graph. The equivalence of the MCGA to the CGA with respect to the acceptance of graph languages is shown. The memory size of the FSA in our MCGA is made proportional to the area (i.e., the total number of nodes) of the input graph, as sugested by Wu and Rosenfeld [loc. cit.]. It is shown how the above two modifications to the original CGA facilitates construction of simpler and faster algorithms for solving weighted graph problems.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68Q80 Cellular automata (computational aspects)
68W99 Algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] 1. A. R. SMITH, Cellular Automata and Formal Languages, in Proceedings, l l t h SWAT, Vol. III, 1970, pp. 216-224.
[2] 2. P. ROSENTIEHL, J. R. FIKSEL and A. HOLLIGER, Intelligent Graphs: Networks of Finite Automata capable of solving Graph Problems, in Graph Theory and Computing, R. C. READ Ed., 1972, pp. 219-265, Academic Press, New York. Zbl0265.94030 MR354198 · Zbl 0265.94030
[3] 3. A. WU and A. ROSENFELD, Cellular Graph Automata I, Information and Control, Vol. 42, 1979, pp. 305-329. MR546343 · Zbl 0424.68029
[4] 4. A. WU and A. ROSENFELD, Cellular Graph Automata II, Information and Control, Vol. 42, 1979, pp. 330-353. Zbl0424.68030 MR546344 · Zbl 0424.68030 · doi:10.1016/S0019-9958(79)90296-1
[5] 5. A. V. AHO, J. E. HOPCROFT and J. D. ULLMAN, Design and Analysis of Computer Algorithms, Addison Wesley, 1974. Zbl0326.68005 MR413592 · Zbl 0326.68005
[6] 6. N. DEO, Graph Theory with Applications to Engineering and Computer Sciences, Prentice Hall, 1974. Zbl0285.05102 MR360322 · Zbl 0285.05102
[7] 7. A. ROSENFELD et al., Sequential and Cellular Graph Automata, Journal of Information Sciences, 1980. Zbl0456.68055 · Zbl 0456.68055 · doi:10.1016/0020-0255(80)90024-9
[8] 8. J. MYLOPOULOS, On the relation of Graph Grammars and Graph Automata, in Proceedings, 13th SWAT, 1972, pp. 108-120.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.