𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Enumeration of the perfect sequences of a chordal graph

✍ Scribed by Yasuko Matsui; Ryuhei Uehara; Takeaki Uno

Book ID
108281655
Publisher
Elsevier Science
Year
2010
Tongue
English
Weight
535 KB
Volume
411
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

πŸ“œ 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

Generating and characterizing the perfec
Generating and characterizing the perfect elimination orderings of a chordal graph
✍ L.S. Chandran; L. Ibarra; F. Ruskey; J. Sawada πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 402 KB

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

The square of a chordal graph
The square of a chordal graph
✍ Frank Harary; Terry A. McKee πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 427 KB

We introduce the closed-neighborhood intersection multigraph as a useful multigraph version of the square of a graph. We characterize those multigraphs which are squares of chordal graphs and include an algorithm to go from the squared chordal graph back to its (unique!) square root. This becomes pa