Title of article
Optimal Dynamic Multicommodity Flows in Networks
Author/Authors
Lozovanu، نويسنده , , Dmitrii and Fonoberova، نويسنده , , Maria، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2006
Pages
8
From page
93
To page
100
Abstract
We present a simple algorithm which maintains the topological order of a directed acyclic graph with n nodes under an online edge insertion sequence in O ( n 2.75 ) time, independent of the number of edges m inserted. For dense DAGs, this is an improvement over the previous best result of O ( min { m 3 2 log n , m 3 2 + n 2 log n } ) Katriel and Bodlaender.
Keywords
dynamic networks , Dynamic flows , Multicommodity flows , maximum flows , minimum cost flows
Journal title
Electronic Notes in Discrete Mathematics
Serial Year
2006
Journal title
Electronic Notes in Discrete Mathematics
Record number
1454361
Link To Document