𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Generating and characterizing the perfect elimination orderings of a chordal graph

✍ Scribed by L.S. Chandran; L. Ibarra; F. Ruskey; J. Sawada

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
402 KB
Volume
307
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

We develop a constant time transposition "oracle" for the set of perfect elimination orderings of chordal graphs. Using this oracle, we can generate a Gray code of all perfect elimination orderings in constant amortized time using known results about antimatroids. Using clique trees, we show how the initialization of the algorithm can be performed in linear time. We also develop two new characterizations of perfect elimination orderings: one in terms of chordless paths, and the other in terms of minimal u-v separators.

πŸ“œ SIMILAR VOLUMES

Perfect elimination orderings of chordal
Perfect elimination orderings of chordal powers of graphs
✍ Andreas BrandstΓ€dt; Victor D. Chepoi; Feodor F. Dragan πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 378 KB

Let G = (V,E) be a finite undirected connected graph. We show that there is a common perfect elimination ordering of all powers of G which represent chordal graphs. Consequently, if G and all of its powers are chordal then all these graphs admit a common perfect elimination ordering. Such an orderin

A generalization of chordal graphs and t
A generalization of chordal graphs and the maximum clique problem
✍ Assef Chmeiss; Philippe JΓ©gou πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 584 KB

A graph is chordal or triangulated if it has no chordless cycle with four or more vertices. Chordal graphs are well known for their combinatorial and algorithmic properties. Here we introduce a generalization of chordal graphs, namely CSGk graphs. Informally, a CSG' graph is a complete graph, and fo

On the interval number of a chordal grap
On the interval number of a chordal graph
✍ Edward R. Scheinerman πŸ“‚ Article πŸ“… 1988 πŸ› John Wiley and Sons 🌐 English βš– 249 KB πŸ‘ 2 views

The interval number of a (simple, undirected) graph G is the least positive integer t such that G is the intersection graph of sets, each of which is the union of t real intervals. A chordal (or triangulated) graph is one with no induced cycles on 4 or more vertices. If G is chordal and has maximum