English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  Online Topological Ordering

Katriel, I., & Bodlaender, H. L. (2005). Online Topological Ordering. In Proceedings of the sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-05) (pp. 443-450). Philadelphia, USA: SIAM.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2730-8 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2731-6
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Katriel, Irit1, Author           
Bodlaender, Hans L., Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: It is shown that the problem of maintaining the topological order of the nodes of a directed acyclic graph while inserting $m$ edges can be solved in $O(\min\{m^{3/2}\log n,m^{3/2}+n^2\log n\})$ time, an improvement over the best known result of $O(mn)$. In addition, we analyze the complexity of the same algorithm with respect to the treewidth $k$ of the underlying undirected graph. We show that the algorithm runs in time $O(mk\log^2 n)$ for general $k$ and that it can be implemented to run in $O(n\log n)$ time on trees, which is optimal. If the input contains cycles, the algorithm detects this.

Details

show
hide
Language(s): eng - English
 Dates: 2005-04-252005
 Publication Status: Issued
 Pages: -
 Publishing info: Philadelphia, USA : SIAM
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 279191
Other: Local-ID: C1256428004B93B8-BF8C20579797338CC1256F870046E540-SODATO2004
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Vancouver, Canada
Start-/End Date: 2005-01-23

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of the sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-05)
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Philadelphia, USA : SIAM
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 443 - 450 Identifier: ISBN: 0-89871-585-7