Graph realization of sets of integers
[ 1 ] Instytut Informatyki, Wydział Informatyki i Telekomunikacji, Politechnika Poznańska | [ P ] employee
2024
scientific article
english
- Computational chemistry
- Graph theory
- Polynomial algorithm
- Structure elucidation
EN Graph theory is used in many areas of chemical sciences, especially in molecular chemistry. It is particularly useful in the structural analysis of chemical compounds and in modeling chemical reactions. One of its applications concerns determining the structural formula of a chemical compound. This can be modeled as a variant of the well-known graph realization problem. In the classical version of the problem, a sequence of natural numbers is given, and the question is whether there exists a graph in which the vertices have degrees equal to the given numbers. In the variant considered in this paper, instead of a sequence of natural numbers, a sequence of sets of natural numbers is given, and the question is whether there exists a multigraph such that each of its vertices has a degree equal to a number from one of the sets. This variant of the graph realization problem matches the nature of the problem of determining the structural formula of a chemical compound better than other variants considered in the literature. We propose a polynomial time exact algorithm solving this variant of the problem.
24.06.2024
1965 - 1981
CC BY (attribution alone)
czasopismo hybrydowe
final published version
at the time of publication
70
1,7 [List 2023]