𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Graph Searching, Elimination Trees, and a Generalization of Bandwidth

✍ Scribed by Fedor V. Fomin; Pinar Heggernes; Jan Arne Telle

Publisher
Springer
Year
2004
Tongue
English
Weight
161 KB
Volume
41
Category
Article
ISSN
0178-4617

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Interval degree and bandwidth of a graph
Interval degree and bandwidth of a graph
✍ Fedor V Fomin; Petr A Golovach πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 395 KB

The interval degree id(G) of a graph G is deΓΏned to be the smallest max-degree of any interval supergraphs of G. One of the reasons for our interest in this parameter is that the bandwidth of a graph is always between id(G)=2 and id(G). We prove also that for any graph G the interval degree of G is

A generalization of simplicial eliminati
A generalization of simplicial elimination orderings
✍ Maffray, FrοΏ½dοΏ½ric; Porto, Oscar; Preissmann, Myriam πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 371 KB

We consider the class of graphs where every induced subgraph possesses a vertex whose neighborhood has no P4 and no 2K2. We prove that Berge's Strong Perfect Graph Conjecture holds for such graphs. The class generalizes several well-known families of perfect graphs, such as triangulated graphs and b

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