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 MATRIX PACKING DOWN problem asks to find a row permutation of
a given (0,1)-matrix in such a way that the total sum of the first
non-zero column indexes is maximized. We study the computational
complexity of this problem. We prove that the MATRIX PACKING DOWN
problem is NP-complete even when restricted to zero trace symmetric
(0,1)-matrices or to (0,1)-matrices with at most two 1's per
column. Also, as intermediate results, we introduce several new simple
graph layout problems which...
To overcome the shortage of cadaveric kidneys available for transplantation, several countries organize systematic kidney exchange programs. The kidney exchange problem can be modelled as a cooperative game between incompatible patient-donor pairs whose solutions are permutations of players representing cyclic donations. We show that the problems to decide whether a given permutation is not (weakly) Pareto optimal are NP-complete.
We study the problem of finding an alternating path having given endpoints and passing through a given set of vertices in edge-colored graphs (a path is alternating if any two consecutive edges are in different colors). In particular, we show that this problem in NP-complete for 2-edge-colored graphs. Then we give a polynomial characterization when we restrict ourselves to 2-edge-colored complete graphs. We also investigate on (s,t)-paths through fixed vertices, i.e. paths of length s+t such that...
For the Traveling Salesman Problem (TSP) on Halin graphs with three types of cost functions: sum, bottleneck and balanced and with arbitrary real edge costs we compute in polynomial time the persistency partition , , of the edge set E, where:
= e ∈ E, e belongs to all optimum solutions,
= e ∈ E, e does not belong to any optimum solution and
= e ∈ E, e belongs to some but not to all optimum solutions.
Currently displaying 1 –
20 of
27