𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on computing graph closures

✍ Scribed by Jeremy P. Spinrad

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
153 KB
Volume
276
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

This note shows that the k-closure of a graph can be computed in time proportional to the size of the output, improving on previous O(n 3 ) algorithms.

πŸ“œ SIMILAR VOLUMES

A Note on Graph Colorings and Graph Poly
A Note on Graph Colorings and Graph Polynomials
✍ Noga Alon; Michael Tarsi πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 230 KB

## dedicated to professor w. t. tutte on the occasion of his eightieth birtday It is known that the chromatic number of a graph G=(V, E) with V= [1, 2, ..., n] exceeds k iff the graph polynomial f G => ij # E, i<j (x i &x j ) lies in certain ideals. We describe a short proof of this result, using

A note on approximating graph genus
A note on approximating graph genus
✍ Jianer Chen; Saroja P. Kanchi; Arkady Kanevsky πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 551 KB
On computing graph minor obstruction set
On computing graph minor obstruction sets
✍ Kevin Cattell; Michael J. Dinneen; Rodney G. Downey; Michael R. Fellows; Michael πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 149 KB

The Graph Minor Theorem of Robertson and Seymour establishes nonconstructively that many natural graph properties are characterized by a ΓΏnite set of forbidden substructures, the obstructions for the property. We prove several general theorems regarding the computation of obstruction sets from other