Loading...
Please wait, while we are loading the content...
Similar Documents
Moplex Elimination Orderings (2001)
| Content Provider | CiteSeerX |
|---|---|
| Author | Berry, Anne Bordat, Jean-Paul |
| Description | Classically, triangulated graphs are characterized and recognized by way of perfect elimination orderings (peo, which correspond to an elimination scheme on simplicial vertices). Algorithm LexBFS computes such a peo eciently, but is also useful for the enumeration of the minimal separators and maximal cliques, which means that the ordering it produces is special. We present an ordering which generalizes a LexBFS-type ordering, by eliminating at each step a set of simplicial vertices (called a moplex). This type of ordering actually characterizes triangulated graphs and easily yields the minimal separators and maximal cliques. We establish a strong relationship between moplex elimination orderings and clique trees. We also extend our results to the problem of embedding an arbitrary graph into a triangulated graph by showing that this process of computing a minimal triangulation is essentially equivalent to forcing a graph into having a simplicial moplex elimination ordering. 1 |
| File Format | |
| Language | English |
| Publisher Date | 2001-01-01 |
| Publisher Institution | First Cologne-Twente Workshop on Graphs |
| Access Restriction | Open |
| Subject Keyword | Elimination Scheme Lexbfs-type Ordering Minimal Triangulation Minimal Separator Maximal Clique Perfect Elimination Ordering Strong Relationship Arbitrary Graph Simplicial Vertex Simplicial Moplex Elimination Clique Tree Triangulated Graph Algorithm Lexbfs Computes Moplex Elimination Ordering |
| Content Type | Text |
| Resource Type | Article |
