𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Toward Characterization of Perfect Elimination Digraphs

✍ Scribed by Haskins, Loren; Rose, Donald J.

Book ID
118153803
Publisher
Society for Industrial and Applied Mathematics
Year
1973
Tongue
English
Weight
771 KB
Volume
2
Category
Article
ISSN
0097-5397

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A Note on Perfect Elimination Digraphs
A Note on Perfect Elimination Digraphs
✍ Kleitman, D. J. πŸ“‚ Article πŸ“… 1974 πŸ› Society for Industrial and Applied Mathematics 🌐 English βš– 355 KB
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

A characterization of Thompson digraphs
A characterization of Thompson digraphs
✍ Dora Giammarresi; Jean-Luc Ponty; Derick Wood; Djelloul Ziadi πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 398 KB

A ΓΏnite-state machine is called a Thompson machine if it can be constructed from an emptyfree regular expression using the construction of Thompson as modiΓΏed by Hopcroft and Ullman. We call the underlying digraph of a Thompson machine a Thompson digraph. We characterize Thompson digraphs and we giv