𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Algorithms and outerplanar conditions for A-trails in plane Eulerian graphs

✍ Scribed by Lars Døvling Andersen; Herbert Fleischner; Susanne Regner

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
834 KB
Volume
85
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

The problem of finding A-trails in plane Eulerian graphs is &'P-complete even for 3-connected graphs, as shown by the first two authors in an earlier paper. In the present paper, we discuss sufficient conditions for the existence of an A-trail in a 2-connected plane Eulerian graph. They generalize the result that simple 2-connected outerplane Eulerian graphs always have A-trails; we give a polynomial algorithm for finding A-trails in such graphs and show that this algorithm also works for certain multigraphs.

📜 SIMILAR VOLUMES

A branch and cut algorithm for the Stein
A branch and cut algorithm for the Steiner problem in graphs
✍ Lucena, A.; Beasley, J. E. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 165 KB 👁 2 views

In this paper, we consider the Steiner problem in graphs, which is the problem of connecting together, at minimum cost, a number of vertices in an undirected graph with nonnegative edge costs. We use the formulation of this problem as a shortest spanning tree (SST) problem with additional constraint