✦ LIBER ✦

A note on the number of N-bit strings with maximum complexity

✍ Scribed by G.J. Chaitin

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 187 KB
Volume: 59
Category: Article
ISSN: 0096-3003
DOI: 10.1016/0096-3003(93)90037-f

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A note on the complexity of family sched

A note on the complexity of family scheduling to minimize the number of late jobs

✍ T. C. Edwin Cheng; Zhaohui Liu; Yakov M. Shafransky 📂 Article 📅 2001 🏛 Springer US 🌐 English ⚖ 65 KB 👁 2 views

The single-machine family scheduling problem of minimizing the number of late jobs has been known to be NP-hard, but whether it is NP-hard in the strong sense is cited as an open problem in several reviews. In this note, we prove that this problem is strongly NP-hard even if all set-up times and pro

A note on the string analog of N = 2 sup

A note on the string analog of N = 2 super-symmetric Yang-Mills

✍ César Gómez; Esperanza López 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 444 KB

On the equivalence in complexity among t

On the equivalence in complexity among three computation problems on maximum number of edge-disjoint s−t paths in a probabilistic graph

✍ Pen Cheng; Shigeru Masuyama 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 396 KB

A note on the line-distinguishing chroma

A note on the line-distinguishing chromatic number and the chromatic index of a graph

✍ N. Zagaglia Salvi 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB 👁 1 views

## Abstract Let λ(__G__) be the line‐distinguishing chromatic number and __x__′(__G__) the chromatic index of a graph __G__. We prove the relation λ(__G__) ≥ __x__′(__G__), conjectured by Harary and Plantholt. © 1993 John Wiley & Sons, Inc.

Note on the reconstruction of infinite g

Note on the reconstruction of infinite graphs with a fixed finite number of components

✍ Thomas Andreae 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 169 KB 👁 1 views

For every positive integer c , we construct a pair G, , H, of infinite, nonisomorphic graphs both having exactly c components such that G, and H, are hypomorphic, i.e., G, and H, have the same families of vertex-deleted subgraphs. This solves a problem of Bondy and Hemminger. Furthermore, the pair G

Note on the series of fully benzenoid hy

Note on the series of fully benzenoid hydrocarbons with a constant number of isomers

✍ Sven J. Cyvin 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 321 KB

There are series of C,H, formulae for fully benzenoid hydrocarbons which correspond to equal numbers of all-benzenoid isomers. These formulae are treated in general terms. Also, other classes of all-benzenoids are defined in relation to a periodic table for fully benzenoid hydrocarbons. Some new enu