๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On the computational complexity of graph closures

โœ Scribed by Angelo Monti

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
375 KB
Volume
57
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Computation of the 0-dual closure for ha
Computation of the 0-dual closure for hamiltonian graphs
โœ Ingo Schiermeyer ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 601 KB

Schiermeyer, I., Computation of the O-dual closure for hamiltonian graphs, Discrete Mathematics 111 (1993) 455-464. The well-known closure concept of Bondy and Chvbtal (1976) is based on degree sums of pairs of nonadjacent vertices. It generalizes six earlier sufficient degree conditions for hamilto

On the Computational Complexity of Finit
On the Computational Complexity of Finite Cellular Automata
โœ K. Sutner ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 932 KB

We study the computational complexity of several problems with the evolution of configurations on finite cellular automata. In many cases, the problems turn out to be complete in their respective classes. For example, the problem of deciding whether a configuration has a predecessor is shown to be N