The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
This paper studies the computational complexity of the proper
interval colored graph problem (PICG), when the input graph
is a colored caterpillar, parameterized by hair length. In order prove our
result we establish a close relationship between the PICG and
a graph layout problem the proper colored layout problem
(PCLP).
We show a dichotomy: the PICG and the
PCLP are NP-complete for colored caterpillars of hair length ≥2, while both problems are in P for colored caterpillars
of hair length <2.
For...
A partitioning algorithm for the Euclidean matching problem in is introduced and analyzed in a probabilistic model. The algorithm uses elements from the fixed dissection algorithm of Karp and Steele (1985) and the Zig-Zag algorithm of Halton and Terada (1982) for the traveling salesman problem. The algorithm runs in expected time and approximates the optimal matching in the probabilistic sense.
We study deterministic one-way communication complexity of functions with Hankel communication matrices. Some structural properties of such matrices are established and applied to the one-way two-party communication complexity of symmetric Boolean functions. It is shown that the number of required communication bits does not depend on the communication direction, provided that neither direction needs maximum complexity. Moreover, in order to obtain an optimal protocol, it is in any case sufficient...
We study deterministic one-way communication complexity
of functions with Hankel communication matrices.
Some structural properties of such matrices are established
and applied to the one-way two-party communication complexity
of symmetric Boolean functions.
It is shown that the number of required communication bits
does not depend on the communication direction, provided that
neither direction needs maximum complexity.
Moreover, in order to obtain an optimal protocol, it is
in any case sufficient...
In on-line computation, the instance of the problem dealt is not
entirely known from the beginning of the solution process, but it
is revealed step-by-step. In this paper we deal with on-line
independent set. On-line models studied until now for this problem
suppose that the input graph is initially empty and revealed
either vertex-by-vertex, or cluster-by-cluster. Here we present a
new on-line model quite different to the ones already studied. It
assumes that a superset of the final graph is initially...
An edge ranking of a graph is a labeling of edges using positive integers such that all paths connecting two edges with the same label visit an intermediate edge with a higher label. An edge ranking of a graph is optimal if the number of labels used is minimum among all edge rankings. As the problem of finding optimal edge rankings for general graphs is NP-hard [12], it is interesting to concentrate on special classes of graphs and find optimal edge rankings for them efficiently. Apart from trees...
Dans cet article, nous essayons de faire le point sur les résultats concernant les aspects combinatoires et algorithmiques des ordres médians et des ordres de Slater des tournois. La plupart des résultats recensés sont tirés de différentes publications ; plusieurs sont originaux.
Currently displaying 61 –
76 of
76