Outputs (5)

Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs (2015)
Presentation / Conference Contribution
Giannopoulou, A., Mertzios, G., & Niedermeier, R. (2015, September). Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs. Presented at 10th International Symposium on Parameterized and Exact Computation (IPEC), Patras, Greece

We study the design of fixed-parameter algorithms for problems already known to be solvable in polynomial time. The main motivation is to get more efficient algorithms for problems with unattractive polynomial running times. Here, we focus on a funda... Read More about Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs.

Ephemeral networks with random availability of links: The case of fast networks (2015)
Journal Article
Akrida, E., Gąsieniec, L., Mertzios, G., & Spirakis, P. (2016). Ephemeral networks with random availability of links: The case of fast networks. Journal of Parallel and Distributed Computing, 87, 109-120. https://doi.org/10.1016/j.jpdc.2015.10.002

We consider here a model of temporal networks, the links of which are available only at certain moments in time, chosen randomly from a subset of the positive integers. We define the notion of the Temporal Diameter of such networks. We also define fa... Read More about Ephemeral networks with random availability of links: The case of fast networks.

The recognition of simple-triangle graphs and of linear-interval orders is polynomial (2015)
Journal Article
Mertzios, G. (2015). The recognition of simple-triangle graphs and of linear-interval orders is polynomial. SIAM Journal on Discrete Mathematics, 29(3), 1150-1185. https://doi.org/10.1137/140963108

Intersection graphs of geometric objects have been extensively studied, due to both their interesting structure and their numerous applications; prominent examples include interval graphs and permutation graphs. In this paper we study a natural graph... Read More about The recognition of simple-triangle graphs and of linear-interval orders is polynomial.

New geometric representations and domination problems on tolerance and multitolerance graphs (2015)
Presentation / Conference Contribution
Giannopoulou, A., & Mertzios, G. (2015, December). New geometric representations and domination problems on tolerance and multitolerance graphs. Presented at 32nd Symposium on Theoretical Aspects of Computer Science (STACS), Munich, Germany

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain amount of overlap without being in conflict. In one of the most natural generalizations of tolerance graphs with direct applications in the comparison of DN... Read More about New geometric representations and domination problems on tolerance and multitolerance graphs.

Optimizing busy time on parallel machines (2015)
Journal Article
Mertzios, G., Shalom, M., Voloshin, A., Wong, P., & Zaks, S. (2015). Optimizing busy time on parallel machines. Theoretical Computer Science, 562, 524-541. https://doi.org/10.1016/j.tcs.2014.10.033

We consider the following fundamental parallel machines scheduling problem in which the input consists of n jobs to be scheduled on a set of identical machines of bounded capacity g, which is the maximal number of jobs that can be processed simultane... Read More about Optimizing busy time on parallel machines.