An algorithm for an Eulerian trail traversing specified edges in given order

DOI10.1016/0166-218X(94)90010-8MaRDI QIDQ1343142zbMATH OpenOpenAlexFDO

Authors Mao-Cheng Cai

Publication date 1 February 1995

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(94)90010-8

zbMATH Keywords

algorithmedge-connectivityEulerian graphEulerian trail

Mathematics Subject Classification ID

Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

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.

Recommendations

• An eulerian trail traversing specified edges in given order
• Algorithms and outerplanar conditions for A-trails in plane Eulerian graphs
• Computing Eulerian trails
• Spanning trails containing given edges
• scientific article; zbMATH DE number 6007896

Cites work

• A Reduction Method for Edge-Connectivity in Graphs
• An eulerian trail traversing specified edges in given order
• scientific article; zbMATH DE number 3825852 (Why is no real title available?)
• scientific article; zbMATH DE number 3906496 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• On some connectivity properties of Eulerian graphs
• Some remarks on Arc‐connectivity, vertex splitting, and orientation in graphs and digraphs

Cited in

(7)

• Computing Eulerian trails
• Searching for a strong double tracing in a graph
• Constant amortized time enumeration of Eulerian trails
• Eulerian walks in temporal graphs
• An eulerian trail traversing specified edges in given order
• Enumerating Eulerian trails via Hamiltonian path enumeration
• The algorithms for the Eulerian cycle and Eulerian trail problems for a multiple graph

This page was built for publication: An algorithm for an Eulerian trail traversing specified edges in given order

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1343142)