Wiener index W(G) of a connected undirected graph G equals the sum of distances between all pairs of vertices in G. In this paper, an effective algorithm for calculating Wiener index of maximal outerplane graphs with a big number n of vertices is offered. The time complexity of the algorithm is O(n 2). The algorithm is fit for manual calculation of Wiener index of small graphs, as well as for its calculation for computer generated graphs.
Download file
Counter downloads: 66
- Title The Wiener index of maximal outerplane graphs
- Headline The Wiener index of maximal outerplane graphs
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 4(26)
- Date:
- DOI
Keywords
индекс Винера, максимальный внешнеплоский граф, хордаль-ный граф, компактное представление хордального графа, graph algorithm, maximal outerplane graph, Wiener index, chordal graph, compact representation of chordal graphAuthors
References
Markenzon L. and Vernet O. Representagoes Computacionais de Grafos. Notas em Matema-tica Aplicada. V.24. Sao Carlos, SP: SBMAC, 2006. 76 p.
Beyer T., Jones W., and Mitchell S. Linear algorithms for isomorphism of Maximal outer-planar graphs. // J. ACM. 1979. V.26. No. 4. P. 603-610.
Markenzon L. and Pereira P. R. C. A compact representation for chordal graphs // Proc. of Workshop on Graphs and Combinatorial Optimization. Gargnano: CTW, 2008. P. 174-176.
Asratian A. S. and Oksimets N. Graphs with hamiltonian balls // Australasian J. Combinator. 1998. V. 17. No. 4. P. 185-198.
Rose D., Tarjan R. E., and Lueker G. Algorithmic aspects of vertex elimination on graphs // SIAM J. Comput. 1976. V.5. No. 2. P. 146-160.
Tarjan R. E., and Yannakakis M. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs // SIAM J. Comput. 1984. V. 13. No. 3. P. 566-579.
Dirac G. A. On rigid circuit graphs // Abh. Math. Sem. Univ. Hamburg. 1967. V. 25. P. 71-76.
Харари Ф. Теория графов. М.: Мир, 1973. 300с.
Felzenszwalb P. F. Representation and detection of deformable shapes // IEEE Trans. Pattern Analys. Machine Intelligence. 2005. V.27. No. 2. P. 208-220.
Bellman R. On a routing problem // Quart. Appl. Math. 1958. V. 16. No. 1. P. 87-90.
Ford Jr. L. R. Network Flow Theory // Paper P-923. Santa Monica, California: RAND Corp., 1956. P. 923.
Mohar B. and Pisanski T. How to compute the Wiener index of a graph. // J. Math. Chem. 1988. V.3. No. 2. P. 267-277.
Dijkstra E. W. A note on two problems in connexion with graphs // Numer. Math. 1959. V. 1. No. 1. P. 269-271.
MUller W.R., Szymanski K., Knop J. V., and Trinajstic N. An algorithm for construction of the molecular distance matrix // J. Comput. Chem. 1987. V. 8. No. 2. P. 170-173.
Soltes L. Transmission in graphs: a bound and vertex removing // Math. Slovaca. 1991. V. 41. No. 1. P. 11-16.
El Marraki M. and Al Hagri G. Calculation of the Wiener index for some particular trees // J. Theor. Appl. Inform. Technology (JATIT). 2010. V.22. No. 2. P. 77-83.
Floyd R. W. Algorithm 97: Shortest Path // Comm. ACM. 1962. V. 5. No. 6. P. 345.
Warshall S. A theorem on Boolean matrices // J. ACM. 1962. V. 9. No. 1. P. 11-12.
Johnson D. B. Efficient algorithms for shortest paths in sparse networks // J. ACM. 1977. V. 24. No. 1. P. 1-13.
Добрынин А. А. Индекс Винера для графов произвольного обхвата и их реберных графов // Сибирский журнал индустриальной математики. 2009. Т. XXII. №4(40). С. 44-50.
Добрынин А. А., Мельников Л. С. Индекс Винера для графов и их реберных графов // Дискретный анализ и исследование операций. 2004. Сер. 2. Т. 11. №2. С. 25-44.
Добрынин А. А., Гутман И. Индекс Винера для деревьев и графов гексагональных систем // Дискретный анализ и исследование операций. 1998. Сер. 2. Т. 5. №2. С. 34-60.
Vukicevic D. and Trinajstic N. Wiener indices of benzenoid graphs // Bulletin of the Chemists and Technologists of Macedonia. 2004. V.23. No. 2. P. 113-129.
Gutman I., Yan W., Yang B. Y., and Yeh Y. N. Generalized Wiener indices of zigzagging pentachains // J. Math. Chem. 2007. V.42. No. 2. P. 103-117.
Gutman I., Yeh Y. N., Lee S. L., and Chen J. C. Wiener numbers of dendrimer // Commum. Math. Chem. 1984. V.30. No. 1. P. 103-115.
Gutman I., Yeh Y. N., Lee S. L., and Luo Y. L. Some recent results in the theory of the Wiener number // Indian J. Chemistry. 1993. V. 32A P. 651-661.
Dobrynin A. А., Entringer R. C., and Gutman I. Wiener index of trees: theory and applications // Acta Appl. Math. 2001. V.66. No.3. P. 211-249.
Федянин Д. Н. Об индексе Винера в последовательности социальных сетей // Тр. 52-й науч. конф. МФТИ «Соременные проблемы фундаментальных и прикладных наук». Ч. I. Радиотехника и кибернетика. Т. 2. М.: МФТИ, 2009. С. 94-97.
Wiener H. Structural determination of paraffin boiling points // J. Amer. Chem. Soc. 1947. V. 69. P. 17-20.
Евстигнеев В. A., Касьянов В. Н. Словарь по графам в информатике. Новосибирск: ООО «Сибирское научное издательство», 2009. 300с.
Blair J. R. S. and Peyton B. An introduction to chordal graphs and clique trees // Graph Theory and Sparse Matrix Computation. N.Y.: Springer Verlag, 1993. P. 1-29.
The Wiener index of maximal outerplane graphs | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2014. № 4(26).
Download full-text version
Counter downloads: 202