A linear-time algorithm for maximum-cardinality matching on cocomparability graphs (2018)
Journal Article
Mertzios, G., Nichterlein, A., & Niedermeier, R. (2018). A linear-time algorithm for maximum-cardinality matching on cocomparability graphs. SIAM Journal on Discrete Mathematics, 32(4), 2820-2835. https://doi.org/10.1137/17m1120920

Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph problems. For general $m$-edge and $n$-vertex graphs, it is well known to be solvable in $O(m\sqrt{n})$ time. We present a linear-time algorithm to f... Read More about A linear-time algorithm for maximum-cardinality matching on cocomparability graphs.

When can graph hyperbolicity be computed in linear time? (2018)
Journal Article
Fluschnik, T., Komusiewicz, C., Mertzios, G., Nichterlein, A., Niedermeier, R., & Talmon, N. (2019). When can graph hyperbolicity be computed in linear time?. Algorithmica, 81(5), 2016-2045. https://doi.org/10.1007/s00453-018-0522-6

Hyperbolicity is a distance-based measure of how close a given graph is to being a tree. Due to its relevance in modeling real-world networks, hyperbolicity has seen intensive research over the last years. Unfortunately, the best known algorithms use... Read More about When can graph hyperbolicity be computed in linear time?.

Binary search in graphs revisited (2018)
Journal Article
Deligkas, A., Mertzios, G., & Spirakis, P. (2019). Binary search in graphs revisited. Algorithmica, 81(5), Article 1757. https://doi.org/10.1007/s00453-018-0501-y

In the classical binary search in a path the aim is to detect an unknown target by asking as few queries as possible, where each query reveals the direction to the target. This binary search algorithm has been recently extended by Emamjomeh-Zadeh et... Read More about Binary search in graphs revisited.

The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs (2018)
Journal Article
Bevern, R., Fluschnik, T., Mertzios, G., Molter, H., Sorge, M., & Suchý, O. (2018). The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs. Discrete Optimization, 30, 20-50. https://doi.org/10.1016/j.disopt.2018.05.002

This work studies the parameterized complexity of finding secluded solutions to classical combinatorial optimization problems on graphs such as finding minimum - separators, feedback vertex sets, dominating sets, maximum independent sets, and vertex... Read More about The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs.

Temporal network optimization subject to connectivity constraints (2018)
Journal Article
Mertzios, G., Michail, O., & Spirakis, P. (2019). Temporal network optimization subject to connectivity constraints. Algorithmica, 81(4), 1416-1449. https://doi.org/10.1007/s00453-018-0478-6

In this work we consider temporal networks, i.e. networks defined by a labeling λ assigning to each edge of an underlying graph G a set of discrete time-labels. The labels of an edge, which are natural numbers, indicate the discrete time moments at w... Read More about Temporal network optimization subject to connectivity constraints.

Temporal vertex cover with a sliding time window (2018)
Conference Proceeding
Akrida, E., Mertzios, G., Spirakis, P., & Zamaraev, V. (2018). Temporal vertex cover with a sliding time window. In I. Chatzigiannakis, C. Kaklamanis, D. Marx, & D. Sannella (Eds.), 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) : Prague, Czech Republic, July 9-13, 2018 ; proceedings (148:1-148:14). https://doi.org/10.4230/lipics.icalp.2018.148

Modern, inherently dynamic systems are usually characterized by a network structure, i.e. an underlying graph topology, which is subject to discrete changes over time. Given a static underlying graph G, a temporal graph can be represented via an assi... Read More about Temporal vertex cover with a sliding time window.

Kernelization Lower Bounds for Finding Constant-Size Subgraphs (2018)
Book Chapter
Fluschnik, T., Mertzios, G., & Nichterlein, A. (2018). Kernelization Lower Bounds for Finding Constant-Size Subgraphs. In F. Manea, R. Miller, & D. Nowotka (Eds.), Sailing routes in the world of computation : 14th Conference on Computability in Europe, CiE 2018, Kiel, Germany, July 30-August 3, 2018. Proceedings (183-193). Springer Verlag. https://doi.org/10.1007/978-3-319-94418-0_19

Kernelization is an important tool in parameterized algorithmics. Given an input instance accompanied by a parameter, the goal is to compute in polynomial time an equivalent instance of the same problem such that the size of the reduced instance only... Read More about Kernelization Lower Bounds for Finding Constant-Size Subgraphs.

Strong bounds for evolution in networks (2018)
Journal Article
Mertzios, G., & Spirakis, P. (2018). Strong bounds for evolution in networks. Journal of Computer and System Sciences, 97, 60-82. https://doi.org/10.1016/j.jcss.2018.04.004

This work studies the generalized Moran process, as introduced by Lieberman et al. [Nature, 433:312-316, 2005]. We introduce the parameterized notions of selective amplifiers and selective suppressors of evolution, i.e. of networks (graphs) with many... Read More about Strong bounds for evolution in networks.