返回Google圖書搜尋

Reachability Substitutes for Planar Digraphs

Irit KatrielMartin KutzMartin Skutella (Mathematician)

出版	MPI Informatik, Bibliothek & Dokumentation, 2005
URL	http://books.google.com.hk/books?id=BRUNtwAACAAJ&hl=&source=gbs_api

註釋Abstract: "Given a digraph G = (V, E) with a set U of vertices marked 'interesting, ' we want to find a smaller digraph H = (Vʹ, Eʹ) with Vʹ [intersecting] U in such a way that the reachabilities amongst those interesting vertices in G and H are the same. So with respect to the reachability relations within U, the digraph H is a substitute for G. We show that while almost all graphs do not have reachability substitutes smaller than [omega]([absolute value U]2/log[absolute value U]), every planar graph has a reachability substitute of size O([absolute value U]log2[absolute value U]). Our result rests on two new structural results for planar dags, a separation procedure and a reachability theorem, which might be of independent interest."