Search

The shortest augmenting path (Sap) algorithm is one of the most classical approaches to the maximum matching and maximum flow problems, e.g., using it Edmonds and Karp (J. ACM 19(2), 248-264 1972) have shown the first strongly polynomial time algorithm for the maximum flow problem. Quite astonishingly, although it has been studied for many years already, this approach is far from being fully understood. This is exemplified by the online bipartite matching problem. In this problem a bipartite graph G = (W ⊎ B, E) is being revealed online, i.e., in each round one vertex from B with its incident edges arrives. After arrival of this vertex we augment the current matching by using shortest augmenting path. It was conjectured by Chaudhuri et al. (INFOCOM'09) that the total length of all augmenting paths found by Sap is O(nlogn)O(nlog n) . However, no better bound than O(n2)O(n2) is known even for trees. In this paper we prove an O(nlog2n)O(nlog2 n) upper bound for the total length of augmenting paths for trees. [ABSTRACT FROM AUTHOR]

We consider distance queries in vertex-labeled planar graphs. For any fixed 0 < ϵ ≤ 1/2 we show how to preprocess a directed planar graph with vertex labels and arc lengths into a data structure that answers queries of the following form. Given a vertex u and a label λ return a (1 + ϵ)-approximation of the distance from u to its closest vertex with label λ. For a directed planar graph with n vertices, such that the ratio of the largest to smallest arc length is bounded by N, the preprocessing time is O(ϵ-2 n lg3 n lg(n N)), the data structure size is O(ϵ-1 n lg(n N)), and the query time is O(lg lg n lg lg(n N) + ϵ-1). We also point out that a vertex label distance oracle for undirected planar graphs suggested in an earlier version of this paper is incorrect. [ABSTRACT FROM AUTHOR]

In this paper we study complexity of an extension of ordered binary decision diagrams (OBDDs) called c-OBDDs on CNFs of bounded (primal graph) treewidth. In particular, we show that for each k ≥ 3 there is a class of CNFs of treewidth k for which the equivalent c-OBDDs are of size Ω( n ). Moreover, this lower bound holds if c-OBDDs are non-deterministic and semantic. Our second result uses the above lower bound to separate the above model from sentential decision diagrams (SDDs). In order to obtain the lower bound, we use a structural graph parameter called matching width. Our third result shows that matching width and pathwidth are linearly related. [ABSTRACT FROM AUTHOR]