Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: Some Nested Dissection Order is Nearly Optimal
Authors: Gilbert, John R.
Keywords: computer science
technical report
Issue Date: Aug-1986
Publisher: Cornell University
Abstract: The minimum fill problem is to reorder the rows and columns of a given sparse symmetric matrix so that its triangular factor is as sparse as possible. Equivalently, it is to find the smallest set of edges whose addition makes a given undirected graph chordal. The problem is known to be NP-complete, and no polynomial-time approximation algorithms are known that provide any nontrivial guarantee for arbitrary graphs (matrices), although some heuristics perform well in practice. Nested dissection is one such heuristic. In this note we prove that every graph with a fixed bound on vertex degree has a nested dissection order that achieves fill within a factor of $O(\logn)$ of minimum. This does not lead to a polynomial-time approximation algorithm, however, because the proof does not give an efficient method for finding the separators required by nested dissection.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
86-767.pdf649.52 kBAdobe PDFView/Open
86-767.ps187.21 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us