登入選單

返回Google圖書搜尋

On Algorithms for Online Topological Ordering and Sorting

Irit Katriel

出版	Max-Planck-Institut für Informatik, 2004
URL	http://books.google.com.hk/books?id=AZQOHQAACAAJ&hl=&source=gbs_api

註釋

Abstract: "We derive several results about algorithms for the online topological ordering and sorting problems. The main result is that a slight variation on an algorithm by Alpern et al. yields an amortized complexity of [square root of m] log n per edge for an n-node m-edge DAG. This is an improvement, for all except very dense graphs, over the best known previous result of O(n) per edge due to Marchetti-Spaccamela et al."