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

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.