Dahlhaus, Elias
(1997).
Minimal Elimination Ordering Inside a Given Chordal Graph.
Springer.
["eprint_fieldopt_monograph_type_preprint" not defined].
|
PDF
zaik1999-356.pdf - Draft Version Download (237kB) | Preview |
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.
| Item Type: | Preprints, Working Papers or Reports (["eprint_fieldopt_monograph_type_preprint" not defined]) | ||||||||
| Creators: |
|
||||||||
| URN: | urn:nbn:de:hbz:38-548401 | ||||||||
| Series Name: | Lecture notes in computer science | ||||||||
| Volume: | 1335 | ||||||||
| Page Range: | pp. 132-143 | ||||||||
| Date: | 1997 | ||||||||
| Publisher: | Springer | ||||||||
| Language: | English | ||||||||
| Faculty: | Faculty of Mathematics and Natural Sciences | ||||||||
| Divisions: | Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science | ||||||||
| Subjects: | Data processing Computer science | ||||||||
| Refereed: | No | ||||||||
| URI: | http://kups.ub.uni-koeln.de/id/eprint/54840 |
Downloads
Downloads per month over past year
Export
Actions (login required)
 |
View Item |