Information flows, graphs and their guessing numbers.

Riis, Søren

Displaying similar documents to “Information flows, graphs and their guessing numbers.”

Note: The Smallest Nonevasive Graph Property

Michał Adamaszek (2014)

Discussiones Mathematicae Graph Theory

Similarity:

A property of n-vertex graphs is called evasive if every algorithm testing this property by asking questions of the form “is there an edge between vertices u and v” requires, in the worst case, to ask about all pairs of vertices. Most “natural” graph properties are either evasive or conjectured to be such, and of the few examples of nontrivial nonevasive properties scattered in the literature the smallest one has n = 6. We exhibit a nontrivial, nonevasive property of 5-vertex graphs...

A graph-theoretic characterization of the core in a homogeneous generalized assignment game

Tadeusz Sozański (2006)

Banach Center Publications

Similarity:

An exchange network is a socioeconomic system in which any two actors are allowed to negotiate and conclude a transaction if and only if their positions-mathematically represented by the points of a connected graph-are joined by a line of this graph. A transaction consists in a bilaterally agreed-on division of a profit pool assigned to a given line. Under the one-exchange rule, every actor is permitted to make no more than one transaction in each negotiation round. Bienenstock and Bonacich...