Minimal Elimination Ordering Inside a Given Chordal Graph
Dahlhaus, Elias
(1997)
Minimal Elimination Ordering Inside a Given Chordal Graph.
Published In:
Graphtheoretic concepts in computer science : 23th international workshop, WG '97, Berlin, Germany, June 18  20, 1997 ; proceedings, Lecture notes in computer science. 1335 Springer 1997, pp. 132143.
Abstract
We consider the following problem, called Relative Minimal Elimination Ordering. Given a graph G=(V,E) which is a subgraph of the chordal graph G'=(V,E'), compute an inclusion minimal chordal graph G''=(V,E''), such that E subseteq E'' subseteq E'. We show that this can be done in O(nm) time. This extends the results of Telle. The algorithm is based only on well known results on chordal graphs. This is an extended version of the paper published in WG 97.
Download: 
Postscript
 Preprinted Version
Download (267kB)  Preview 

Editorial actions:  View Item (Login required) 
Item Type:  Proceedings article 

Citations:  No citation data. 
Uncontrolled Keywords:  chordal graphs Gauss elimination minimum degree heuristics nested dissection sparse matrices 
Subjects: 

Divisions:  Mathematical Institute 
Related URLs: 
ZAIK Number:  zaik1999356 

Depositing User:  Archive Admin 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  19 Dec 2011 09:45 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/356 