EuDML | Browse

Items

All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1 Next

Displaying 1 – 20 of 27

Packing of (0, 1)-matrices

Stéphane Vialette (2006)

RAIRO - Theoretical Informatics and Applications

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...

Parallelizable algebras.

Matthias Ragaz (1987)

Archiv für mathematische Logik und Grundlagenforschung

Pareto optimality in the kidney exchange problem

Viera Borbeľová, Katarína Cechlárová (2008)

Kybernetika

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.

Partial order with duality and consistent choice problem

Martin Gavalec (1996)

Mathematica Slovaca

Partitioning Arrangements of Lines, I: An Efficient Deterministic Algorithm.

P.K. Agarwal (1990)

Discrete & computational geometry

Paths through fixed vertices in edge-colored graphs

W. S. Chou, Y. Manoussakis, O. Megalakaki, M. Spyratos, Zs. Tuza (1994)

Mathématiques et Sciences Humaines

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...

Permanents, Pfaffian orientations, and even directed circuits.

Robertson, Neil, Seymour, P.D., Thomas, Robin (1999)

Annals of Mathematics. Second Series

Persistency in the Traveling Salesman Problem on Halin graphs

Vladimír Lacko (2000)

Discussiones Mathematicae Graph Theory

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 $E_{A l l}$ , $E_{S o m e}$ , $E_{N o n e}$ of the edge set E, where: $E_{A l l}$ = e ∈ E, e belongs to all optimum solutions, $E_{N o n e}$ = e ∈ E, e does not belong to any optimum solution and $E_{S o m e}$ = e ∈ E, e belongs to some but not to all optimum solutions.