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 infinite sequences. (Sur la complexité des suites infinies.)
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 Reinforcement in Graphs
We show that the decision problem for p-reinforcement, p-total rein- forcement, total restrained reinforcement, and k-rainbow reinforcement are NP-hard for bipartite graphs.
On the complexity of the Double Digest Problem
On the complexity of the hidden weighted bit function for various BDD models
On the Complexity of the Hidden Weighted Bit Function for Various BDD Models
Ordered binary decision diagrams (OBDDs) and several more general BDD models have turned out to be representations of Boolean functions which are useful in applications like verification, timing analysis, test pattern generation or combinatorial optimization. The hidden weighted bit function (HWB) is of particular interest, since it seems to be the simplest function with exponential OBDD size. The complexity of this function with respect to different circuit models, formulas, and various...
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 computation of covert channel capacity
We address the problem of computing the capacity of a covert channel, modeled as a nondeterministic transducer. We give three possible statements of the notion of “covert channel capacity” and relate the different definitions. We then provide several methods allowing the computation of lower and upper bounds for the capacity of a channel. We show that, in some cases, including the case of input-deterministic channels, the capacity of the channel can be computed exactly (e.g. in the form...
On the computation of the GCD of 2-D polynomials
The main contribution of this work is to provide an algorithm for the computation of the GCD of 2-D polynomials, based on DFT techniques. The whole theory is implemented via illustrative examples.
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.
On the computational complexity of (O,P)-partition problems
We prove that for any additive hereditary property P > O, it is NP-hard to decide if a given graph G allows a vertex partition V(G) = A∪B such that G[A] ∈ 𝓞 (i.e., A is independent) and G[B] ∈ P.
On the computer algebra implementation of the least squares method on the nonnegative orthant.