𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A 222pn upper bound on the complexity of Presburger Arithmetic

✍ Scribed by Derek C. Oppen

Publisher
Elsevier Science
Year
1978
Tongue
English
Weight
605 KB
Volume
16
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A probabilistic upper bound for the edge
A probabilistic upper bound for the edge identification complexity of graphs
✍ Eberhard Triesch πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 344 KB

Given a finite graph G=( V, E), what is the minimum number c(G) of incidence tests which are needed in the worst case to identify an unknown edge e\*EE? The number c(G) was first studied by Aigner and Triesch (1988), where it was shown that for almost all graphs in the random graph model where d(n)

The Order Upper Bound on Parity Embeddin
The Order Upper Bound on Parity Embedding of a Graph
✍ Thomas Zaslavsky πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 398 KB

A graph 1 is parity embedded in a surface if a closed path in the graph is orientation preserving or reversing according to whether its length is even or odd. The parity demigenus of 1 is the minimum of 2&/(S) (where / is the Euler characteristic) over all surfaces S in which 1 can be parity embedde

A New Upper Bound on the Cheeger Number
A New Upper Bound on the Cheeger Number of a Graph
✍ Sorin Dragomir; Elisabetta Barletta πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 117 KB

Using a technique developed by A. Nilli (1991, Discrete Math. 91, 207 210), we estimate from above the Cheeger number of a finite connected graph G of small degree (2(G) 5) admitting sufficiently distant edges. ## 2001 Academic Press Let G=(V(G), E(G)) be a finite connected graph. The Cheeger numb