On Shank's algorithm for modular square roots.
On some Basic Properties of the Kolmogorov Complexity
On some packing problem related to dynamic storage allocation
On the Algebraic Complexity of Sets of Functions
On the approximability of comparing genomes with duplicates.
On the average number of registers needed to evaluate a special class of backtrack trees
On the Ball Spanned by Balls.
On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls.
On the Complexity of a Single Cell in Certain Arrangements of Surfaces Related to Motion Planning.
On the complexity of computable real sequences
On the complexity of covering nodes by K node-disjoint cycles
On the complexity of events recognizable in real time
On the complexity of parametrizing curves.
On the Complexity of Polyhedral Separability.
On the complexity of problems on simple games
Simple games cover voting systems in which a single alternative, such as a bill or an amendment, is pitted against the status quo. A simple game or a yes-no voting system is a set of rules that specifies exactly which collections of “yea” votes yield passage of the issue at hand. Each of these collections of “yea” voters forms a winning coalition. We are interested in performing a complexity analysis on problems defined on such families of games. This analysis as usual depends on the game representation...
On the complexity of problems on simple games
Simple games cover voting systems in which a single alternative, such as a bill or an amendment, is pitted against the status quo. A simple game or a yes-no voting system is a set of rules that specifies exactly which collections of “yea” votes yield passage of the issue at hand. Each of these collections of “yea” voters forms a winning coalition. We are interested in performing a complexity analysis on problems defined on such families of games....
On the complexity of the Double Digest Problem
On the complexity of the Shapley-Scarf economy with several types of goods
In the Shapley-Scarf economy each agent is endowed with one unit of an indivisible good (house) and wants to exchange it for another, possibly the most preferred one among the houses in the market. In this economy, core is always nonempty and a core allocation can be found by the famous Top Trading Cycles algorithm. Recently, a modification of this economy, containing Q >= 2 types of goods (say, houses and cars for Q=2) has been introduced. We show that if the number of agents is 2, a complete...
On the complexity of the subgraph problem
On the computational complexity of centers locating in a graph
It is shown that the problem of finding a minimum -basis, the -center problem, and the -median problem are -complete even in the case of such communication networks as planar graphs with maximum degree 3. Moreover, a near optimal -center problem is also -complete.