Outputs (75)

An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs (2010)
Journal Article
Mertzios, G., & Unger, W. (2010). An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs. Mathematics in Computer Science, 3(1), 85-96. https://doi.org/10.1007/s11786-009-0004-y

In this paper we consider the k-fixed-endpoint path cover problem on proper interval graphs, which is a generalization of the path cover problem. Given a graph G and a set T of k vertices, a k-fixed-endpoint path cover of G with respect to T is a set... Read More about An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs.

The Recognition of Tolerance and Bounded Tolerance Graphs (2010)
Presentation / Conference Contribution
Mertzios, G., Sau, I., Zaks, S., Marion, J.-Y., & Schwentick, T. (2010, March). The Recognition of Tolerance and Bounded Tolerance Graphs. Presented at 27th International Symposium on Theoretical Aspects of Computer Science (STACS), Nancy, France

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This subclass of perfect graphs has been extensively studied, due to both its interesting structure and its num... Read More about The Recognition of Tolerance and Bounded Tolerance Graphs.

Preemptive scheduling of equal-length jobs in polynomial time (2010)
Journal Article
Mertzios, G., & Unger, W. (2010). Preemptive scheduling of equal-length jobs in polynomial time. Mathematics in Computer Science, 3(1), 73-84. https://doi.org/10.1007/s11786-009-0003-z

We study the preemptive scheduling problem of a set of n jobs with release times and equal processing times on a single machine. The objective is to minimize the sum of the weighted completion times åi=1nwiCini=1wiCi of the jobs. We propose for this... Read More about Preemptive scheduling of equal-length jobs in polynomial time.

A Precompiler to Reduce the Memory Footprint of Multiscale PDE Solvers in C++ (2010)
Journal Article
Bungartz, H., Eckhardt, W., Weinzierl, T., & Zenger, C. (2010). A Precompiler to Reduce the Memory Footprint of Multiscale PDE Solvers in C++. Future Generation Computer Systems, 26(1), 175-182. https://doi.org/10.1016/j.future.2009.05.011

Binary Codes for Packet Error and Packet Loss Correction in Store and Forward (2010)
Presentation / Conference Contribution
Gadouleau, M., & Goupil, A. (2010, January). Binary Codes for Packet Error and Packet Loss Correction in Store and Forward. Presented at International ITG Conference on Source and Channel Coding, Siegen, Germany

One-to-many node-disjoint paths in (n,k)-star graphs (2010)
Journal Article
Stewart, I., & Xiang, Y. (2010). One-to-many node-disjoint paths in (n,k)-star graphs. Discrete Applied Mathematics, 158(1), 62-70. https://doi.org/10.1016/j.dam.2009.08.013

We present an algorithm which given a source node and a set of n−1 target nodes in the (n,k)-star graph Sn,k, where all nodes are distinct, builds a collection of n−1 node-disjoint paths, one from each target node to the source. The collection of pat... Read More about One-to-many node-disjoint paths in (n,k)-star graphs.

Implicit surface reconstruction and feature detection with a learning algorithm (2010)
Presentation / Conference Contribution
Kaye, D., & Ivrissimtzis, I. (2010, September). Implicit surface reconstruction and feature detection with a learning algorithm. Presented at Theory and Practice of Computer Graphics, Sheffield, UK

We propose a new algorithm for implicit surface reconstruction and feature detection. The algorithm is based on a self organising map with the connectivity of a regular 3D grid that can be trained into an implicit representation of surface data. The... Read More about Implicit surface reconstruction and feature detection with a learning algorithm.

On solution concepts for matching games (2010)
Presentation / Conference Contribution
Biro, P., Kern, W., & Paulusma, D. (2010, December). On solution concepts for matching games. Presented at 7th Annual Conference on Theory and Applications of Models of Computation, Prague, Czech Republic

A matching game is a cooperative game (N,v) defined on a graph G = (N,E) with an edge weighting . The player set is N and the value of a coalition S ⊆ N is defined as the maximum weight of a matching in the subgraph induced by S. First we present an... Read More about On solution concepts for matching games.

On contracting graphs to fixed pattern graphs (2010)
Presentation / Conference Contribution
't, H. P. V., Kaminski, M., Paulusma, D., Szeider, S., & Thilikos, D. M. (2010, December). On contracting graphs to fixed pattern graphs. Presented at 36th Conference on Current Trends in Theory and Practice of Computer Science, Špindleruv Mlýn, Czech Republic

For a fixed graph H, the H-Contractibility problem asks if a graph is H-contractible, i.e., can be transformed into H via a series of edge contractions. The computational complexity classification of this problem is still open. So far, H has a domina... Read More about On contracting graphs to fixed pattern graphs.

Packing bipartite graphs with covers of complete bipartite graphs (2010)
Presentation / Conference Contribution
Chalopin, J., & Paulusma, D. (2010, December). Packing bipartite graphs with covers of complete bipartite graphs. Presented at 7th International Conference on Algorithms and Complexity, Rome, Italy

For a set of graphs, a perfect -packing (-factor) of a graph G is a set of mutually vertex-disjoint subgraphs of G that each are isomorphic to a member of and that together contain all vertices of G. If G allows a covering (locally bijective homomorp... Read More about Packing bipartite graphs with covers of complete bipartite graphs.