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

Optimal query complexity bounds for finding graphs

โœ Scribed by Sung-Soon Choi; Jeong Han Kim

Publisher
Elsevier Science
Year
2010
Tongue
English
Weight
336 KB
Volume
174
Category
Article
ISSN
0004-3702

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

A bound for the complexity of a simple g
A bound for the complexity of a simple graph
โœ Robert Grone; Russell Merris ๐Ÿ“‚ Article ๐Ÿ“… 1988 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 310 KB

Let G be a simple (nonfat graph wiih degree sequeme dl, dz, l . . , d,. The ~~~~~ of spanning trees of G is bounded above by

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)