Skip to main content

Research Repository

Advanced Search

Outputs (311)

Matrix and graph orders derived from locally constrained graph homomorphisms (2005)
Presentation / Conference Contribution
Fiala, J., Paulusma, D., & Telle, J. A. (2023, August). Matrix and graph orders derived from locally constrained graph homomorphisms. Presented at 30th International Symposium on Mathematical Foundations of Computer Science : MFCS 2005, Gdansk, Poland

We consider three types of locally constrained graph homomorphisms: bijective, injective and surjective. We show that the three orders imposed on graphs by existence of these three types of homomorphisms are partial orders. We extend the well-known c... Read More about Matrix and graph orders derived from locally constrained graph homomorphisms.

The computational complexity of the elimination problem in generalized sports competitions (2004)
Journal Article
Kern, W., & Paulusma, D. (2004). The computational complexity of the elimination problem in generalized sports competitions. Discrete Optimization, 1(2), 205-214. https://doi.org/10.1016/j.disopt.2003.12.003

Consider a sports competition among various teams playing against each other in pairs (matches) according to a previously determined schedule. At some stage of the competition one may ask whether a particular team still has a (theoretical) chance to... Read More about The computational complexity of the elimination problem in generalized sports competitions.

Run-time mapping of applications to a heterogeneous reconfigurable tiled system on chip architecture (2004)
Presentation / Conference Contribution
Smit, L., Smit, G., Hurink, J., Broersma, H., Paulusma, D., & Wolkotte, P. (2004, December). Run-time mapping of applications to a heterogeneous reconfigurable tiled system on chip architecture. Presented at Proceedings. 2004 IEEE International Conference on Field- Programmable Technology (IEEE Cat. No.04EX921)

This work evaluates an algorithm that maps a number of communicating processes to a heterogeneous tiled system on chip (SoC) architecture at run-time. The mapping algorithm minimizes the total amount of energy consumption, while still providing an ad... Read More about Run-time mapping of applications to a heterogeneous reconfigurable tiled system on chip architecture.

Run-time assignment of tasks to multiple heterogeneous processors (2004)
Presentation / Conference Contribution
Smit, L., Smit, G., Hurink, J., Broersma, H., Paulusma, D., & Wolkotte, P. (2004, December). Run-time assignment of tasks to multiple heterogeneous processors. Presented at 5th PROGRESS Symposium on Embedded Systems., Nieuwegein, The Netherlands

This paper describes the implementation and evaluation of an algorithm that maps a number of communicating processes to a heterogeneous tiled System on Chip (SoC) architecture at run-time. The mapping algorithm minimizes the total amount of energy co... Read More about Run-time assignment of tasks to multiple heterogeneous processors.

The complexity of graph contractions (2003)
Presentation / Conference Contribution
Levin, A., Paulusma, D., & Woeginger, G. (2003, June). The complexity of graph contractions. Presented at WG 2003: Graph-Theoretic Concepts in Computer Science, Elspeet, The Netherlands

The Computational Complexity of the Role Assignment Problem (2003)
Presentation / Conference Contribution
Fiala, J., & Paulusma, D. (2003, June). The Computational Complexity of the Role Assignment Problem. Presented at ICALP 2003: Automata, Languages and Programming, Eindhoven, The Netherlands

Matching games : the least core and the nucleolus (2003)
Journal Article
Kern, W., & Paulusma, D. (2003). Matching games : the least core and the nucleolus. Mathematics of Operations Research, 28(2), 294-308. https://doi.org/10.1287/moor.28.2.294.14477

A matching game is a cooperative game defined by a graph G = (V, E). The player set is V and the value of a coalition S # V is defined as the size of a maximum matching in the subgraph induced by S. We show that the nucleolus of such games can be com... Read More about Matching games : the least core and the nucleolus.

Two extensions of the Shapley value for cooperative games (2001)
Journal Article
Driessen, T., & Paulusma, D. (2001). Two extensions of the Shapley value for cooperative games. Mathematical Methods of Operations Research, 53(1), 35-49. https://doi.org/10.1007/s001860000099

Two extensions of the Shapley value are given. First we consider a probabilistic framework in which certain consistent allocation rules such as the Shapley value are characterized. The second generalization of the Shapley value is an extension to the... Read More about Two extensions of the Shapley value for cooperative games.

The new FIFA rules are hard: complexity aspects of sports competitions (2001)
Journal Article
Kern, W., & Paulusma, D. (2001). The new FIFA rules are hard: complexity aspects of sports competitions. Discrete Applied Mathematics, 108(3), 317-323. https://doi.org/10.1016/s0166-218x%2800%2900241-9

Consider a soccer competition among various teams playing against each other in pairs (matches) according to a previously determined schedule. At some stage of the competition one may ask whether a particular team still has a (theoretical) chance to... Read More about The new FIFA rules are hard: complexity aspects of sports competitions.