An $\tilde{O}(n^{2.5})$-Time Algorithm for Online Topological Ordering

Simple item page
dc.creatorLiu, Hsiao-Fei
dc.creatorChao, Kun-Mao
dc.date2008-04-24
dc.date2008-08-23
dc.date.accessioned2026-07-07T09:57:45Z
dc.date.available2026-07-07T09:57:45Z
dc.descriptionWe present an $\tilde{O}(n^{2.5})$-time algorithm for maintaining the topological order of a directed acyclic graph with $n$ vertices while inserting $m$ edges.
dc.descriptionBetter results have been proposed in the following paper: Haeupler, Kavitha, Mathew, Sen, Tarjan: Faster Algorithms for Incremental Topological Ordering. ICALP (1) 2008: 421-433
dc.identifierhttps://arxiv.org/abs/0804.3860
dc.identifierhttp://arxiv.org/abs/0804.3860
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/167463
dc.subjectComputer Science and Game Theory
dc.subjectData Structures and Algorithms
dc.subjectF.2.2
dc.titleAn $\tilde{O}(n^{2.5})$-Time Algorithm for Online Topological Ordering
dc.typetext

Files

Collections

arXiv