GRAPH-SUBGRAPH ISOMORPHISM PROBLEM SOLVING FOR ORGANIZATION RESOURCES DISTRIBUTION

M. Ilyashenko

Abstract


The paper presents graph-analytical approach for organizations resources distribution. It based on graph-subgraph isomorphism
algorithm for weighted and labeled graphs and can be considered as development of graph-subgraph isomorphism algorithm for weighted
graphs proposed before.
Paper describes requirements and specifics of human and technical resources reservation in modern distributed organizations, that can have rather complicated structure, taking into account relations between available resources, and specifics of requirements in resources provided by complicated tasks that need to be solved by organizations. All types of resources considered as weighted and labeled graphs. Next presented advanced version of graph-subgraph isomorphism algorithm enhanced to work with graphs both weighted and labeled by vertexes. Provided full set of preliminary conditions aim to narrow main combinatorial part of algorithm, where branch and bound
method used to find final substitution.

Keywords


resources reservation, graph-subgraph isomorphism, weighted graphs, labeled graphs, graph-analytical approach

References


Haijun, Zhang. Research on co-reservation in the manufacturing grid system / Haijun Zhang, Yefa Hu, Zude Zhou // The International Journal of Advanced Manufacturing Technology. – 2010. – Volume 47, Issue 5–8. – P. 699–717.

Christoph, Langguth. Optimizing resource allocation for scientific workflows using advance reservations / Christoph Langguth, Heiko Schuldt // Proceeding SSDBM’10 Proceedings of the 22nd international conference on Scientific and statistical database management. – Springer-Verlag. – 2010. – P. 434–451.

Ильяшенко, М. Б. Алгоритм нахождения графподграф изоморфизма для взвешенных графов и его применение / Ильяшенко М. Б. // Радиоэлектроника, информатика, управление. – 2007. – № 1. – С. 62–68.

Ильяшенко, М. Б. Разработка и исследование параллельного алгоритма проверки граф-подграф изоморфизма / Ильяшенко М. Б. // Радиоэлектроника, информатика, управление. – 2006. – № 1. – С. 63–69.

Пинчук, В. П. Распознование изоморфности графов: ПНВ-алгоритм / В. П. Пинчук // Складні системи і процеси. – 2002. – № 1. – С. 4–11.

Пинчук, В. П. Основанная на волновом разложении система инвариантов для простых графов и алгоритм распознавания изоморфности / В. П. Пинчук // Киев, 1995. – Деп. в ГНТБ Украины 10.05.95, N 1002 – Ук 95.


GOST Style Citations






DOI: https://doi.org/10.15588/1607-3274-2014-1-8



Copyright (c) 2014 M. Ilyashenko

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Address of the journal editorial office:
Editorial office of the journal «Radio Electronics, Computer Science, Control»,
Zaporizhzhya National Technical University, 
Zhukovskiy street, 64, Zaporizhzhya, 69063, Ukraine. 
Telephone: +38-061-769-82-96 – the Editing and Publishing Department.
E-mail: rvv@zntu.edu.ua

The reference to the journal is obligatory in the cases of complete or partial use of its materials.