On Complexity of Algorithmic
Problems on Skew-Symmetric Graphs
Abstract
Two equivalent nonstandard notions of graphs,
namely skew-symmetric and
bidirected, will be discussed during the talk. We shall give a survey on
polynomially solvable problems on these graphs. Also, a number of
applications to certain well-known combinatorial optimization problems
will be explained.
Author's articles on this topic can be found on his
page.