𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The even-path problem for graphs and digraphs

✍ Scribed by Andrea S. Lapaugh; Christos H. Papadimitriou

Publisher
John Wiley and Sons
Year
1984
Tongue
English
Weight
357 KB
Volume
14
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

The Isomorphism Problem For Directed Pat
The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
✍ L. Babel; I.N. Ponomarenko; G. Tinhofer πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 237 KB

This paper deals with the isomorphism problem of directed path graphs and rooted directed path graphs. Both graph classes belong to the class of chordal graphs, and for both classes the relative complexity of the isomorphism problem is yet unknown. We prove that deciding isomorphism of directed path

A Simple Parallel Algorithm for the Sing
A Simple Parallel Algorithm for the Single-Source Shortest Path Problem on Planar Digraphs
✍ Jesper L. TrΓ€ff; Christos D. Zaroliagis πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 216 KB

We present a simple parallel algorithm for the single-source shortest path problem in planar digraphs with nonnegative real edge weights. The algorithm runs on the EREW PRAM model of parallel computation in O((n 2= +n 1&= ) log n) time, performing O(n 1+= log n) work for any 0<=<1Γ‚2. The strength of

Tools for studying paths and cycles in d
Tools for studying paths and cycles in digraphs
✍ Delorme, C.; Ordaz, O.; Quiroz, D. πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 251 KB

The main goal of this work was to describe the basic elements constituting a specialized knowledge base in the field of paths and circuits in digraphs. This knowledge base contains commented on examples with textual and graphical descriptions, invariants, relations among invariants, and theorems. It