Paths through K-specified edges in a linear graph

MaRDI QIDQ690196zbMATH OpenFDO

Authors Harjeet Arora, Santosh Kumar

Publication date 12 June 1994

Published in Opsearch (Search for Journal in Brave)

zbMATH Keywords

algorithmEulerian graphlinear graphpath

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35)

Review text

Let \(G\) be a simple, connected and undirected graph, let \(K\) be a set of edges of \(G\), and let \(s\) and \(d\) be two different vertices of \(G\). This paper gives an algorithm to find all paths in \(G\) from \(s\) to \(d\), whose edge-set contains \(K\). The result is based on the fact that, if \(P\) is such a path, the remaining ones take the form \(P \oplus E\), where \(E\) is an Eulerian graph.

Recommendations

• Cycles and paths through specified vertices in k-connected graphs
• Paths and edge-connectivity in graphs
• Paths in graphs
• scientific article; zbMATH DE number 762736
• scientific article; zbMATH DE number 1151850
• Long paths and cycles through specified vertices in k-connected graphs.
• scientific article; zbMATH DE number 4099351
• Paths and trails in edge-colored graphs
• Paths and Trails in Edge-Colored Graphs
• Graphs of edge-intersecting and non-splitting paths

Cited in

(1)

• An algorithm to find all paths between two nodes in a graph

This page was built for publication: Paths through K-specified edges in a linear graph

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