Skip to main content

Research Repository

Advanced Search

Outputs (79)

A new characterization of P6-free graphs (2010)
Journal Article
Hof, P. V. '., & Paulusma, D. (2010). A new characterization of P6-free graphs. Discrete Applied Mathematics, 158(7), 731-740. https://doi.org/10.1016/j.dam.2008.08.025

We study P6-free graphs, i.e., graphs that do not contain an induced path on six vertices. Our main result is a new characterization of this graph class: a graph G is P6-free if and only if each connected induced subgraph of G on more than one vertex... Read More about A new characterization of P6-free graphs.

A general algorithm for detecting faults under the comparison diagnosis model (2010)
Presentation / Conference Contribution
Stewart, I. (2010, April). A general algorithm for detecting faults under the comparison diagnosis model. Presented at 24th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2010), Atlanta, Georgia, U.S.A

We develop a widely applicable algorithm to solve the fault diagnosis problem in certain distributed-memory multiprocessor systems in which there are a limited number of faulty processors. In particular, we prove that if the underlying graph G = (V,E... Read More about A general algorithm for detecting faults under the comparison diagnosis model.

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.

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.

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.

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.

Path factors and parallel knock-out schemes of almost claw-free graphs (2010)
Presentation / Conference Contribution
Johnson, M., Paulusma, D., & Wood, C. (2010, December). Path factors and parallel knock-out schemes of almost claw-free graphs. Presented at 19th International Workshop on Combinatorial Algorithms, Nagoya

An H1, {H2}-factor of a graph G is a spanning subgraph of G with exactly one component isomorphic to the graph H1 and all other components (if there are any) isomorphic to the graph H2.We completely characterise the class of connected almost claw-fre... Read More about Path factors and parallel knock-out schemes of almost claw-free graphs.