An algorithm for an Eulerian trail traversing specified edges in given order
type: Item
instance of: scholarly article
title: An algorithm for an Eulerian trail traversing specified edges in given order
zbMATH Open document ID: 0811.05042
DOI: 10.1016/0166-218X(94)90010-8
published in: Discrete Applied Mathematics
publication date: 1995-02-01T00:00:00Z
review text: A connected graph is Eulerian if it has a closed trail which includes every edge of \(G\); such a trail is called an Eulerian trail. Given an Eulerian graph \(G = (V,E)\) and edges \(\{e_ 1,e_ 2, \dots, e_ s\} \subset E\), an interesting question is whether there exists an Eulerian trail of the form \(e_ 1, \dots, e_ 2, \dots, e_ s, \dots\). Cai and Fleischner proved that if \(G\) is \(2k\)-edge-connected then for every subset \(S = \{e_ 1,e_ 2, \dots, e_ s\}\) of \(E\) and an arbitrary orientation of a subset \(T\) of \(S\) such that \(| S| + | T| \leq 2k + 1\) there exists an Eulerian trail of the form \(e_ 1, \dots, e_ 2, \dots, e_ s, \dots\) in accordance with the orientation of \(T\). In this paper Cai gives an \(O(| V|^{8/3} | E|^ 2)\) time algorithm for finding such an Eulerian trail.
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 716323
zbMATH Keywords: edge-connectivity
zbMATH Keywords: Eulerian trail
zbMATH Keywords: Eulerian graph
zbMATH Keywords: algorithm
author: Mao-Cheng Cai
reviewed by: Martin Middendorf
MaRDI profile type: Publication
cites work: An eulerian trail traversing specified edges in given order
cites work: Q3684121
cites work: Q3672016
cites work: Some remarks on Arc‐connectivity, vertex splitting, and orientation in graphs and digraphs
cites work: On some connectivity properties of Eulerian graphs
cites work: A Reduction Method for Edge-Connectivity in Graphs
cites work: Q4739657
full work available at URL: 0166-218x(94)90010-8
OpenAlex ID: W2085206979
description: scientific article; zbMATH DE number 716323