ALGORITHMS FOR SOLVING SYSTEMS OF EQUATIONS OVER VARIOUS CLASSES OF FINITE GRAPHS [АЛГОРИТМЫ РЕШЕНИЯ СИСТЕМ УРАВНЕНИЙ НАД РАЗЛИЧНЫМИ КЛАССАМИ КОНЕЧНЫХ ГРАФОВ] Full article
| Journal |
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika)
ISSN: 2071-0410 , E-ISSN: 2311-2263 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2021, Number: 53, Pages: 89-102 Pages count : 14 DOI: 10.17223/20710410/53/6 | ||||
| Tags | Computational complexity; Graph; System of equations | ||||
| Authors |
|
||||
| Affiliations |
|
Abstract:
The aim of the paper is to study and to solve finite systems of equations over finite undirected graphs. Equations over graphs are atomic formulas of the language L consisting of the set of constants (graph vertices), the binary vertex adjacency predicate and the equality predicate. It is proved that the problem of checking compatibility of a system of equations S with k variables over an arbitrary simple n-vertex graph Γ is NP-complete. The computational complexity of the procedure for checking compatibility of a system of equations S over a simple graph Γ and the procedure for finding a general solution of this system is calculated. The computational complexity of the algorithm for solving a system of equations S with k variables over an arbitrary simple n-vertex graph Γ involving these procedures is O(k2nk/2+1(k + n)2) for n > 3. Polynomially solvable cases are distinguished: systems of equations over trees, forests, bipartite and complete bipartite graphs. Polynomial time algorithms for solving these systems with running time O(k2n(k + n)2) are proposed. © 2021 Tomsk State University. All rights reserved.
Cite:
Il'Ev A.V.
, Il'Ev V.P.
ALGORITHMS FOR SOLVING SYSTEMS OF EQUATIONS OVER VARIOUS CLASSES OF FINITE GRAPHS [АЛГОРИТМЫ РЕШЕНИЯ СИСТЕМ УРАВНЕНИЙ НАД РАЗЛИЧНЫМИ КЛАССАМИ КОНЕЧНЫХ ГРАФОВ]
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2021. N53. P.89-102. DOI: 10.17223/20710410/53/6 WOS Scopus OpenAlex
ALGORITHMS FOR SOLVING SYSTEMS OF EQUATIONS OVER VARIOUS CLASSES OF FINITE GRAPHS [АЛГОРИТМЫ РЕШЕНИЯ СИСТЕМ УРАВНЕНИЙ НАД РАЗЛИЧНЫМИ КЛАССАМИ КОНЕЧНЫХ ГРАФОВ]
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2021. N53. P.89-102. DOI: 10.17223/20710410/53/6 WOS Scopus OpenAlex
Identifiers:
| Web of science: | WOS:000716473900006 |
| Scopus: | 2-s2.0-85122571577 |
| OpenAlex: | W4206708663 |