文章基本信息

标题：All-Pairs 2-Reachability in O(n^w log n) Time
本地全文：下载
作者：Loukas Georgiadis ; Daniel Graf ; Giuseppe F. Italiano 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：80
页码：74:1-74:14
DOI：10.4230/LIPIcs.ICALP.2017.74
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：In the 2-reachability problem we are given a directed graph G and we wish to determine if there are two (edge or vertex) disjoint paths from u to v, for given pair of vertices u and v. In this paper, we present an algorithm that computes 2-reachability information for all pairs of vertices in O(n^w log n) time, where n is the number of vertices and w is the matrix multiplication exponent. Hence, we show that the running time of all-pairs 2-reachability is only within a log factor of transitive closure. Moreover, our algorithm produces a witness (i.e., a separating edge or a separating vertex) for all pair of vertices where 2-reachability does not hold. By processing these witnesses, we can compute all the edge- and vertex-dominator trees of G in O(n^2) additional time, which in turn enables us to answer various connectivity queries in O(1) time. For instance, we can test in constant time if there is a path from u to v avoiding an edge e, for any pair of query vertices u and v, and any query edge e, or if there is a path from u to v avoiding a vertex w, for any query vertices u, v, and w.
关键词：2-reachability; All Dominator Trees; Directed Graphs; Boolean Matrix Multiplication