Linear amortized time enumeration algorithms for compatible Euler trails in edge-colored graphs

Yuhang Bai; Zhiwei Guo; Shenggui Zhang; Yandong Bai

doi:10.1007/s10878-023-01005-w

Linear amortized time enumeration algorithms for compatible Euler trails in edge-colored graphs

Yuhang Bai
, Zhiwei Guo
, Shenggui Zhang
, Yandong Bai

School of Mathematics and Statistics

Northwestern Polytechnical University Xian
Yan'an University

Research output: Contribution to journal › Article › peer-review

Abstract

A compatible Euler trail (tour) in an edge-colored graph is an Euler trail (tour) in which each two edges traversed consecutively along the Euler trail (tour) have distinct colors. In this paper, we show that the problem of counting compatible Euler trails in edge-colored graphs is # P-complete, and develop O(mN) time algorithms for enumerating compatible Euler trails (tours) in edge-colored graphs with m edges and N compatible Euler trails (tours). It is worth mentioning that our algorithms can run in O(N) time when there is no vertex v with degree 4 and maximum monochromatic degree 2.

Original language	English
Article number	73
Journal	Journal of Combinatorial Optimization
Volume	45
Issue number	2
DOIs	https://doi.org/10.1007/s10878-023-01005-w
State	Published - Mar 2023

Keywords

Compatible Euler trail
Edge-colored graph
Enumeration algorithm
Linear amortized time

Access to Document

10.1007/s10878-023-01005-w

Cite this

@article{f0b4f4b7e08544418f15a06d4c8bcb3d,

title = "Linear amortized time enumeration algorithms for compatible Euler trails in edge-colored graphs",

abstract = "A compatible Euler trail (tour) in an edge-colored graph is an Euler trail (tour) in which each two edges traversed consecutively along the Euler trail (tour) have distinct colors. In this paper, we show that the problem of counting compatible Euler trails in edge-colored graphs is \# P-complete, and develop O(mN) time algorithms for enumerating compatible Euler trails (tours) in edge-colored graphs with m edges and N compatible Euler trails (tours). It is worth mentioning that our algorithms can run in O(N) time when there is no vertex v with degree 4 and maximum monochromatic degree 2.",

keywords = "Compatible Euler trail, Edge-colored graph, Enumeration algorithm, Linear amortized time",

author = "Yuhang Bai and Zhiwei Guo and Shenggui Zhang and Yandong Bai",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2023",

month = mar,

doi = "10.1007/s10878-023-01005-w",

language = "英语",

volume = "45",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "2",

}

TY - JOUR

T1 - Linear amortized time enumeration algorithms for compatible Euler trails in edge-colored graphs

AU - Bai, Yuhang

AU - Guo, Zhiwei

AU - Zhang, Shenggui

AU - Bai, Yandong

PY - 2023/3

Y1 - 2023/3

N2 - A compatible Euler trail (tour) in an edge-colored graph is an Euler trail (tour) in which each two edges traversed consecutively along the Euler trail (tour) have distinct colors. In this paper, we show that the problem of counting compatible Euler trails in edge-colored graphs is # P-complete, and develop O(mN) time algorithms for enumerating compatible Euler trails (tours) in edge-colored graphs with m edges and N compatible Euler trails (tours). It is worth mentioning that our algorithms can run in O(N) time when there is no vertex v with degree 4 and maximum monochromatic degree 2.

AB - A compatible Euler trail (tour) in an edge-colored graph is an Euler trail (tour) in which each two edges traversed consecutively along the Euler trail (tour) have distinct colors. In this paper, we show that the problem of counting compatible Euler trails in edge-colored graphs is # P-complete, and develop O(mN) time algorithms for enumerating compatible Euler trails (tours) in edge-colored graphs with m edges and N compatible Euler trails (tours). It is worth mentioning that our algorithms can run in O(N) time when there is no vertex v with degree 4 and maximum monochromatic degree 2.

KW - Compatible Euler trail

KW - Edge-colored graph

KW - Enumeration algorithm

KW - Linear amortized time

UR - https://www.scopus.com/pages/publications/85149965280

U2 - 10.1007/s10878-023-01005-w

DO - 10.1007/s10878-023-01005-w

M3 - 文章

AN - SCOPUS:85149965280

SN - 1382-6905

VL - 45

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 2

M1 - 73

ER -

Linear amortized time enumeration algorithms for compatible Euler trails in edge-colored graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this