Please note that eDoc will be permanently shut down in the first quarter of 2021!      Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Institute: MPI für Informatik     Collection: Algorithms and Complexity Group     Display Documents



ID: 279191.0, MPI für Informatik / Algorithms and Complexity Group
Online Topological Ordering
Authors:Katriel, Irit; Bodlaender, Hans L.
Language:English
Publisher:SIAM
Place of Publication:Philadelphia, USA
Date of Publication (YYYY-MM-DD):2005
Title of Proceedings:Proceedings of the sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-05)
Start Page:443
End Page:450
Place of Conference/Meeting:Vancouver, Canada
(Start) Date of Conference/Meeting
 (YYYY-MM-DD):
2005-01-23
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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.
Last Change of the Resource (YYYY-MM-DD):2005-04-25
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
Identifiers:LOCALID:C1256428004B93B8-BF8C20579797338CC1256F870046E540-...
ISBN:0-89871-585-7
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.