Outputs (7)

On the intersection of tolerance and cocomparability graphs (2010)
Presentation / Conference Contribution
Mertzios, G., & Zaks, S. (2010, December). On the intersection of tolerance and cocomparability graphs. Presented at 21st International Symposium on Algorithms and Computation (ISAAC), Jeju Island, Korea

It has been conjectured by Golumbic and Monma in 1984 that the intersection of tolerance and cocomparability graphs coincides with bounded tolerance graphs. Since cocomparability graphs can be efficiently recognized, a positive answer to this conject... Read More about On the intersection of tolerance and cocomparability graphs.

Placing regenerators in optical networks to satisfy multiple sets of requests (2010)
Presentation / Conference Contribution
Mertzios, G., Sau, I., Shalom, M., & Zaks, S. (2010, July). Placing regenerators in optical networks to satisfy multiple sets of requests. Presented at 37th International Colloquium on Automata, Languages and Programming (ICALP), Bordeaux, France

The placement of regenerators in optical networks has become an active area of research during the last years. Given a set of lightpaths in a network G and a positive integer d, regenerators must be placed in such a way that in any lightpath there ar... Read More about Placing regenerators in optical networks to satisfy multiple sets of requests.

Window-games between TCP flows (2010)
Journal Article
Efraimidis, P., Tsavlidis, L., & Mertzios, G. (2010). Window-games between TCP flows. Theoretical Computer Science, 411(31-33), 2798-2817. https://doi.org/10.1016/j.tcs.2010.03.031

We consider network congestion problems between TCP flows and define a new game, the Window-game, which models the problems of network congestion caused by the competing flows. Analytical and experimental results show the relevance of the Window-game... Read More about Window-games between TCP flows.

A new intersection model and improved algorithms for tolerance graphs (2010)
Presentation / Conference Contribution
Mertzios, G., Sau, I., & Zaks, S. (2010, June). A new intersection model and improved algorithms for tolerance graphs. Presented at 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Montpellier, France

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This class of graphs, which generalizes in a natural way both interval and permutation graphs, has attracted ma... Read More about A new intersection model and improved algorithms for 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.

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.