ГлавнаяАрхивИндекс Винера максимальных внешнеплоских графов

Индекс Винера максимальных внешнеплоских графов | Прикладная дискретная математика. 2014. № 4(26).

Рассматривается инвариант W(G) связных неориентированных графов G, равный сумме расстояний между всеми парами вершин графа G. Предлагается эффективный алгоритм расчёта матрицы расстояний и индекса Винера максимальных внешнеплоских графов с большим количеством вершин. Временная сложность алгоритма O(n 2). Алгоритм удобен как для ручного расчёта индекса Винера небольших графов, так и для расчёта индекса Винера графов, сгенерированных компьютерной программой.
  • Title Индекс Винера максимальных внешнеплоских графов
  • Headline Индекс Винера максимальных внешнеплоских графов
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 4(26)
  • Date:
  • DOI
Ключевые слова
индекс Винера, максимальный внешнеплоский граф, хордаль-ный граф, компактное представление хордального графа, graph algorithm, maximal outerplane graph, Wiener index, chordal graph, compact representation of chordal graph
Авторы
Ссылки
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.
Индекс Винера максимальных внешнеплоских графов | Прикладная дискретная математика. 2014. № 4(26).
Индекс Винера максимальных внешнеплоских графов | Прикладная дискретная математика. 2014. № 4(26).