Path problems in skew-symmetric graphs (Q2563512)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Path problems in skew-symmetric graphs |
scientific article |
Statements
Path problems in skew-symmetric graphs (English)
0 references
3 August 1997
0 references
This paper concerns path problems in skew-symmetric graphs. A skew-symmetric graph is a digraph \(G=(V,E)\) together with a mapping \(\sigma\) of \(V\cup E\) onto itself such that (i) \(\sigma\) is an involution \((\sigma(x)\neq x\) and \(\sigma(\sigma(x))=x)\); (ii) \(\sigma(v)\in V\) for every \(v\in V\); (iii) \(\sigma(e)=(\sigma(v),\sigma(u))\) for every \(e=(u,v)\in E\). Generalizations of the standard graph reachability and shortest path problems are studied. The authors establish combinatorial solvability criteria and duality relations for skew-symmetric path problems and use these to design efficient algorithms for these problems. The algorithms are competitive with the fastest algorithms for the standard problems.
0 references
skew-symmetric graphs
0 references
digraph
0 references
graph reachability
0 references
shorgest path
0 references
duality
0 references
path problems
0 references
efficient algorithms
0 references