| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4651431 | Discrete Mathematics | 2006 | 6 Pages |
Abstract
We show that it is possible to find a minimal fill ordering of a graph in O(n2.69)O(n2.69) time. Previous algorithms for the problem required Ω(n3)Ω(n3) time on dense graphs. The algorithm uses fast matrix multiplication to produce the same ordering of vertices as Tarjan's well known LEX-M algorithm.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Dieter Kratsch, Jeremy Spinrad,