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

A Tight Upper Bound on the Probabilistic Embedding of Series-Parallel Graphs

โœ Scribed by Emek, Yuval; Peleg, David

Book ID
118197062
Publisher
Society for Industrial and Applied Mathematics
Year
2010
Tongue
English
Weight
258 KB
Volume
23
Category
Article
ISSN
0895-4801

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

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 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)