Some polynomial subclasses of the Eulerian walk problem for a multiple graph
In this paper, we study undirected multiple graphs of any natural multiplicity $k>1$. There are edges of three types: ordinary edges, multiple edges and multi-edges. Each edge of the last two types is a union of $k$ linked edges, which connect 2 or $(k+1)$ vertices, correspondingly. The linked ed...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2024-09-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/1881 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | In this paper, we study undirected multiple graphs of any natural multiplicity $k>1$. There are edges of three types: ordinary edges, multiple edges and multi-edges. Each edge of the last two types is a union of $k$ linked edges, which connect 2 or $(k+1)$ vertices, correspondingly. The linked edges should be used simultaneously. If a vertex is incident to a multiple edge, it can be also incident to other multiple edges and it can be the common end of $k$ linked edges of some multi-edge. If a vertex is the common end of some multi-edge, it cannot be the common end of another multi-edge. We study the problem of finding the Eulerian walk (the cycle or the trail) in a multiple graph, which generalizes the classical problem for an ordinary graph. The multiple Eulerian walk problem is NP-hard. We prove the polynomiality of two subclasses of the multiple Eulerian walk problem and elaborate the polynomial algorithms. In the first subclass, we set a constraint on the ordinary edges reachability sets, which are the subsets of vertices joined by ordinary edges only. In the second subclass, we set a constraint on the quasi-vertices degrees in the graph with quasi-vertices. The structure of this ordinary graph reflects the structure of the multiple graph, and each quasi-vertex is determined by $k$ indices of the ordinary edges reachability sets, which are incident to some multi-edge. |
|---|---|
| ISSN: | 1818-1015 2313-5417 |