登入選單

返回Google圖書搜尋

Maintaining the 3-edge-connected Components of a Graph On-line

Columbia University. Department of Computer ScienceZvi Galil

出版	Department of Computer Science, Columbia University, 1991
URL	http://books.google.com.hk/books?id=xeg8HAAACAAJ&hl=&source=gbs_api

註釋

Abstract: "We study the problem of maintaining the 3-edge- connected components of a graph undergoing repeated dynamic modifications, such as edge and vertex insertions. We show how to answer whether two vertices belong to the same 3-edge-connected component of a connected graph that is undergoing only edge insertions. Any sequence of q query and updates on an n-vertex graph can be performed in O((n + q)[alpha](q, n)) time."