Skip to main content

Research Repository

Advanced Search

Outputs (113)

Brief Announcement: On the Existence of δ-Temporal Cliques in Random Simple Temporal Graphs (2024)
Conference Proceeding
Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2024). Brief Announcement: On the Existence of δ-Temporal Cliques in Random Simple Temporal Graphs. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024) (27:1-27:5). https://doi.org/10.4230/LIPIcs.SAND.2024.27

We consider random simple temporal graphs in which every edge of the complete graph K_n appears once within the time interval [0,1] independently and uniformly at random. Our main result is a sharp threshold on the size of any maximum δ-clique (namel... Read More about Brief Announcement: On the Existence of δ-Temporal Cliques in Random Simple Temporal Graphs.

Temporal Graph Realization from Fastest Paths (2024)
Conference Proceeding
Klobas, N., Mertzios, G., Molter, H., & Spirakis, P. (2024). Temporal Graph Realization from Fastest Paths. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024) (16:1-16:18). https://doi.org/10.4230/LIPIcs.SAND.2024.16

In this paper we initiate the study of the temporal graph realization problem with respect to the fastest path durations among its vertices, while we focus on periodic temporal graphs. Given an n × n matrix D and a Δ ∈ ℕ, the goal is to construct a Δ... Read More about Temporal Graph Realization from Fastest Paths.

Graphs with minimum fractional domatic number (2023)
Journal Article
Gadouleau, M., Harms, N., Mertzios, G. B., & Zamaraev, V. (2024). Graphs with minimum fractional domatic number. Discrete Applied Mathematics, 343, 140-148. https://doi.org/10.1016/j.dam.2023.10.020

The domatic number of a graph is the maximum number of vertex disjoint dominating sets that partition the vertex set of the graph. In this paper we consider the fractional variant of this notion. Graphs with fractional domatic number 1 are exactly th... Read More about Graphs with minimum fractional domatic number.

Computing maximum matchings in temporal graphs (2023)
Journal Article
Mertzios, G., Molter, H., Niedermeier, R., Zamaraev, V., & Zschoche, P. (2023). Computing maximum matchings in temporal graphs. Journal of Computer and System Sciences, https://doi.org/10.1016/j.jcss.2023.04.005

Temporal graphs are graphs whose topology is subject to discrete changes over time. Given a static underlying graph G, a temporal graph is represented by assigning a set of integer time-labels to every edge e of G, indicating the discrete time steps... Read More about Computing maximum matchings in temporal graphs.

Payment scheduling in the Interval Debt Model (2023)
Conference Proceeding
Friedetzky, T., Kutner, D., Mertzios, G., Stewart, I., & Trehan, A. (2023). Payment scheduling in the Interval Debt Model. . https://doi.org/10.1007/978-3-031-23101-8_18

The networks-based study of financial systems has received considerable attention in recent years, but seldom explicitly incorporated the dynamic aspects of such systems. We consider this problem setting from the temporal point of view, and we introd... Read More about Payment scheduling in the Interval Debt Model.

The complexity of growing a graph (2022)
Conference Proceeding
Mertzios, G., Michail, O., Skretas, G., Spirakis, P., & Theofilatos, M. (2022). The complexity of growing a graph. In ALGOSENSORS 2022: Algorithmics of Wireless Networks (123-137). https://doi.org/10.1007/978-3-031-22050-0_9

We study a new algorithmic process of graph growth. The process starts from a single initial vertex u0 and operates in discrete timesteps, called slots. In every slot t ≥ 1, the process updates the current graph instance to generate the next graph in... Read More about The complexity of growing a graph.

Interference-free walks in time: Temporally disjoint paths (2022)
Journal Article
Klobas, N., Mertzios, G., Molter, H., Niedermeier, R., & Zschoche, P. (2022). Interference-free walks in time: Temporally disjoint paths. Autonomous Agents and Multi-Agent Systems, 37, Article 1. https://doi.org/10.1007/s10458-022-09583-5

We investigate the computational complexity of finding temporally disjoint paths or walks in temporal graphs. There, the edge set changes over discrete time steps and a temporal path (resp. walk) uses edges that appear at monotonically increasing tim... Read More about Interference-free walks in time: Temporally disjoint paths.

Equitable scheduling on a single machine (2022)
Journal Article
Heeger, K., Hermelin, D., Mertzios, G., Molter, H., Niedermeier, R., & Shabtay, D. (2023). Equitable scheduling on a single machine. Journal of Scheduling, 26(2), 209-225. https://doi.org/10.1007/s10951-022-00754-6

We introduce a natural but seemingly yet unstudied variant of the problem of scheduling jobs on a single machine so as to minimize the number of tardy jobs. The novelty of our new variant lies in simultaneously considering several instances of the pr... Read More about Equitable scheduling on a single machine.

The complexity of computing optimum labelings for temporal connectivity (2022)
Conference Proceeding
Klobas, N., Mertzios, G., Molter, H., & Spirakis, P. (2022). The complexity of computing optimum labelings for temporal connectivity. . https://doi.org/10.4230/lipics.mfcs.2022.62

A graph is temporally connected if there exists a strict temporal path, i.e., a path whose edges have strictly increasing labels, from every vertex u to every other vertex v. In this paper we study temporal design problems for undirected temporally c... Read More about The complexity of computing optimum labelings for temporal connectivity.

The complexity of temporal vertex cover in small-degree graphs (2022)
Conference Proceeding
Hamm, T., Klobas, N., Mertzios, G., & Spirakis, P. (2022). The complexity of temporal vertex cover in small-degree graphs. . https://doi.org/10.1609/aaai.v36i9.21259

Temporal graphs naturally model graphs whose underlying topology changes over time. Recently, the problems Temporal Vertex Cover (or TVC) and Sliding-Window Temporal Vertex Cover (or ∆- TVC for time-windows of a fixed-length ∆) have been established... Read More about The complexity of temporal vertex cover in small-degree graphs.

Interference-free walks in time: temporally disjoint paths (2021)
Conference Proceeding
Klobas, N., Mertzios, G., Molter, H., Niedermeier, R., & Zschoche, P. (2021). Interference-free walks in time: temporally disjoint paths. . https://doi.org/10.24963/ijcai.2021/563

We investigate the computational complexity of finding temporally disjoint paths or walks in temporal graphs. There, the edge set changes over discrete time steps and a temporal path (resp. walk) uses edges that appear at monotonically increasing tim... Read More about Interference-free walks in time: temporally disjoint paths.

The complexity of transitively orienting temporal graphs (2021)
Conference Proceeding
Mertzios, G., Molter, H., Renken, M., Spirakis, P., & Zschoche, P. (2021). The complexity of transitively orienting temporal graphs. In F. Bonchi, & S. J. Puglisi (Eds.), . https://doi.org/10.4230/lipics.mfcs.2021.75

In a temporal network with discrete time-labels on its edges, entities and information can only “flow” along sequences of edges whose time-labels are non-decreasing (resp. increasing), i.e. along temporal (resp. strict temporal) paths. Nevertheless,... Read More about The complexity of transitively orienting temporal graphs.

Equitable scheduling on a single machine (2021)
Conference Proceeding
Heeger, K., Hermelin, D., Mertzios, G., Molter, H., Niedermeier, R., & Shabtay, D. (2021). Equitable scheduling on a single machine. . https://doi.org/10.1609/aaai.v35i13.17404

We introduce a natural but seemingly yet unstudied generalization of the problem of scheduling jobs on a single machine so as to minimize the number of tardy jobs. Our generalization lies in simultaneously considering several instances of the problem... Read More about Equitable scheduling on a single machine.

The temporal explorer who returns to the base (2021)
Journal Article
Akrida, E., Mertzios, G., Spirakis, P., & Raptopoulos, C. (2021). The temporal explorer who returns to the base. Journal of Computer and System Sciences, 120, 179-193. https://doi.org/10.1016/j.jcss.2021.04.001

We study here the problem of exploring a temporal graph when the underlying graph is a star. The aim of the exploration problem in a temporal star is finding a temporal walk which starts and finishes at the center of the star, and visits all leaves.... Read More about The temporal explorer who returns to the base.

Sliding window temporal graph coloring (2021)
Journal Article
Mertzios, G., Molter, H., & Zamaraev, V. (2021). Sliding window temporal graph coloring. Journal of Computer and System Sciences, 120, 97-115. https://doi.org/10.1016/j.jcss.2021.03.005

Graph coloring is one of the most famous computational problems with applications in a wide range of areas such as planning and scheduling, resource allocation, and pattern matching. So far coloring problems are mostly studied on static graphs, which... Read More about Sliding window temporal graph coloring.

Deleting edges to restrict the size of an epidemic in temporal networks (2021)
Journal Article
Enright, J., Meeks, K., Mertzios, G., & Zamaraev, V. (2021). Deleting edges to restrict the size of an epidemic in temporal networks. Journal of Computer and System Sciences, 119, 60-77. https://doi.org/10.1016/j.jcss.2021.01.007

Spreading processes on graphs are a natural model for a wide variety of real-world phenomena, including information spread over social networks and biological diseases spreading over contact networks. Often, the networks over which these processes sp... Read More about Deleting edges to restrict the size of an epidemic in temporal networks.

Exact and approximate algorithms for computing a second Hamiltonian cycle (2020)
Conference Proceeding
Deligkas, A., Mertzios, G., Spirakis, P., & Zamaraev, V. (2020). Exact and approximate algorithms for computing a second Hamiltonian cycle. In J. Esparza, & D. Král (Eds.), 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) (21:1-21:13). https://doi.org/10.4230/lipics.mfcs.2020.27

A classic result by Stockmeyer [Stockmeyer, 1974] gives a non-elementary lower bound to the emptiness problem for star-free generalized regular expressions. This result is intimately connected to the satisfiability problem for interval temporal logic... Read More about Exact and approximate algorithms for computing a second Hamiltonian cycle.

The Power of Linear-Time Data Reduction for Maximum Matching (2020)
Journal Article
Mertzios, G., Nichterlein, A., & Niedermeier, R. (2020). The Power of Linear-Time Data Reduction for Maximum Matching. Algorithmica, 82(12), 3521-3565. https://doi.org/10.1007/s00453-020-00736-0

Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph primitives. For m-edge and n-vertex graphs, it is well-known to be solvable in O(mn−−√) time; however, for several applications this running time is... Read More about The Power of Linear-Time Data Reduction for Maximum Matching.

How fast can we reach a target vertex in stochastic temporal graphs? (2020)
Journal Article
Akrida, E. C., Mertzios, G. B., Nikoletseas, S., Raptopoulos, C., Spirakis, P. G., & Zmaraev, V. (2020). How fast can we reach a target vertex in stochastic temporal graphs?. Journal of Computer and System Sciences, 114, 65-83. https://doi.org/10.1016/j.jcss.2020.05.005

Temporal graphs abstractly model real-life inherently dynamic networks. Given a graph G, a temporal graph with G as the underlying graph is a sequence of subgraphs (snapshots) of G, where . In this paper we study stochastic temporal graphs, i.e. stoc... Read More about How fast can we reach a target vertex in stochastic temporal graphs?.

Computing maximum matchings in temporal graphs (2020)
Conference Proceeding
Mertzios, G., Molter, H., Niedermeier, R., Zamaraev, V., & Zschoche, P. (2020). Computing maximum matchings in temporal graphs. In C. Paul, & M. Blaser (Eds.), 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) (27:1-27:14). https://doi.org/10.4230/lipics.stacs.2020.27

Temporal graphs are graphs whose topology is subject to discrete changes over time. Given a static underlying graph G, a temporal graph is represented by assigning a set of integer time-labels to every edge e of G, indicating the discrete time steps... Read More about Computing maximum matchings in temporal graphs.

Deleting edges to restrict the size of an epidemic in temporal networks (2019)
Conference Proceeding
Enright, J., Meeks, K., Mertzios, G., & Zamaraev, V. (2019). Deleting edges to restrict the size of an epidemic in temporal networks. In P. Rossmanith, P. Heggernes, & J. Katoen (Eds.), 44th International Symposium on Mathematical Foundations of Computer Science (57:1-57:15). https://doi.org/10.4230/lipics.mfcs.2019.57

Spreading processes on graphs are a natural model for a wide variety of real-world phenomena, including information or behaviour spread over social networks, biological diseases spreading over contact or trade networks, and the potential flow of good... Read More about Deleting edges to restrict the size of an epidemic in temporal networks.

Temporal vertex cover with a sliding time window (2019)
Journal Article
Akrida, E., Mertzios, G., Spirakis, P., & Zamaraev, V. (2020). Temporal vertex cover with a sliding time window. Journal of Computer and System Sciences, 107, 108-123. https://doi.org/10.1016/j.jcss.2019.08.002

Modern, inherently dynamic systems are usually characterized by a network structure which is subject to discrete changes over time. Given a static underlying graph, a temporal graph can be represented via an assignment of a set of integer time-labels... Read More about Temporal vertex cover with a sliding time window.

How fast can we reach a target vertex in stochastic temporal graphs? (2019)
Conference Proceeding
Akrida, E. C., Mertzios, G. B., Nikoletseas, S., Christoforos, R., Spirakis, P. G., & Zamaraev, V. (2019). How fast can we reach a target vertex in stochastic temporal graphs?. In C. Baier, I. Chatzigiannakis, P. Flocchini, & S. Leonardi (Eds.), 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) (131:1-131:14). https://doi.org/10.4230/lipics.icalp.2019.131

Temporal graphs are used to abstractly model real-life networks that are inherently dynamic in nature, in the sense that the network structure undergoes discrete changes over time. Given a static underlying graph G=(V,E), a temporal graph on G is a s... Read More about How fast can we reach a target vertex in stochastic temporal graphs?.

Sliding Window Temporal Graph Coloring (2019)
Conference Proceeding
Mertzios, G., Molter, H., & Zamaraev, V. (2019). Sliding Window Temporal Graph Coloring. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (7667-7674). https://doi.org/10.1609/aaai.v33i01.33017667

Graph coloring is one of the most famous computational problems with applications in a wide range of areas such as planning and scheduling, resource allocation, and pattern matching. So far coloring problems are mostly studied on static graphs, which... Read More about Sliding Window Temporal Graph Coloring.

The temporal explorer who returns to the base (2019)
Conference Proceeding
Akrida, E., Mertzios, G., & Spirakis, P. (2019). The temporal explorer who returns to the base. In P. Heggernes (Ed.), Algorithms and Complexity (CIAC 2019); 11th International Conference, CIAC 2019, Rome, Italy, May 27–29, 2019 ; proceedings (13-24). https://doi.org/10.1007/978-3-030-17402-6_2

In this paper we study the problem of exploring a temporal graph (i.e. a graph that changes over time), in the fundamental case where the underlying static graph is a star on n vertices. The aim of the exploration problem in a temporal star is to fin... Read More about The temporal explorer who returns to the base.

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.

Binary search in graphs revisited (2017)
Conference Proceeding
Deligkas, A., Mertzios, G., & Spirakis, P. (2017). Binary search in graphs revisited. In K. G. Larsen, H. L. Bodlaender, & J. Raskin (Eds.), 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) : August 21-25, 2017, Aalborg (Denmark) ; proceedings. https://doi.org/10.4230/lipics.mfcs.2017.20

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 Power of Linear-Time Data Reduction for Maximum Matching (2017)
Conference Proceeding
Mertzios, G., Nichterlein, A., & Niedermeier, R. (2017). The Power of Linear-Time Data Reduction for Maximum Matching. In K. G. Larsen, H. L. Bodlaender, & J. Raskin (Eds.), 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) : August 21-25, 2017, Aalborg (Denmark) ; proceedings. https://doi.org/10.4230/lipics.mfcs.2017.46

Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph primitives. For m-edge and n-vertex graphs, it is well-known to be solvable in O(m\sqrt{n}) time; however, for several applications this running time... Read More about The Power of Linear-Time Data Reduction for Maximum Matching.

When can graph hyperbolicity be computed in linear time? (2017)
Conference Proceeding
Fluschnik, T., Komusiewicz, C., Mertzios, G., Nichterlein, A., Niedermeier, R., & Talmon, N. (2017). When can graph hyperbolicity be computed in linear time?. In F. Ellen, A. Kolokolova, & J. Sack (Eds.), Algorithms and data structures : 15th International Symposium, WADS 2017, St. John’s, NL, Canada, July 31 – August 2, 2017 ; proceedings (397-408). https://doi.org/10.1007/978-3-319-62127-2_34

Hyperbolicity measures, in terms of (distance) metrics, 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 pra... Read More about When can graph hyperbolicity be computed in linear time?.

Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs (2017)
Journal Article
Giannopoulou, A. C., Mertzios, G. B., & Niedermeier, R. (2017). Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs. Theoretical Computer Science, 689, 67-95. https://doi.org/10.1016/j.tcs.2017.05.017

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.

The complexity of optimal design of temporally connected graphs (2017)
Journal Article
Akrida, E., Gasieniec, L., Mertzios, G., & Spirakis, P. (2017). The complexity of optimal design of temporally connected graphs. Theory of Computing Systems, 61(3), 907-944. https://doi.org/10.1007/s00224-017-9757-x

We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs of n vertices, where each edge has an associated set of discrete availability instances (labels). A journey from vertex u t... Read More about The complexity of optimal design of temporally connected graphs.

The computational complexity of weighted greedy matching (2017)
Conference Proceeding
Deligkas, A., Mertzios, G., & Spirakis, P. (2017). The computational complexity of weighted greedy matching. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17) : Hilton, San Francisco, Union Square, February 4, 2017 – February 10 (466-472)

Motivated by the fact that in several cases a matching in a graph is stable if and only if it is produced by a greedy algorithm, we study the problem of computing a maximum weight greedy matching on weighted graphs, termed GREEDYMATCHING. In wide con... Read More about The computational complexity of weighted greedy matching.

Finding secluded places of special interest in graphs (2017)
Conference Proceeding
Bevern, R., Fluschnik, T., Mertzios, G., Molter, H., Sorge, M., & Suchý, O. (2017). Finding secluded places of special interest in graphs. In J. Guo, & D. Hermelin (Eds.), 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) : August 24-26, 2016, Aarhus, Denmark (5:1-5:16). https://doi.org/10.4230/lipics.ipec.2016.5

Finding a vertex subset in a graph that satisfies a certain property is one of the most-studied topics in algorithmic graph theory. The focus herein is often on minimizing or maximizing the size of the solution, that is, the size of the desired verte... Read More about Finding secluded places of special interest in graphs.

Identification, location–domination and metric dimension on interval and permutation graphs. I. Bounds (2017)
Journal Article
Foucaud, F., Mertzios, G., Naserasr, R., Parreau, A., & Valicov, P. (2017). Identification, location–domination and metric dimension on interval and permutation graphs. I. Bounds. Theoretical Computer Science, 668, 43-58. https://doi.org/10.1016/j.tcs.2017.01.006

We consider the problems of finding optimal identifying codes, (open) locating–dominating sets and resolving sets of an interval or a permutation graph. In these problems, one asks to find a subset of vertices, normally called a solution set, using w... Read More about Identification, location–domination and metric dimension on interval and permutation graphs. I. Bounds.

Graph editing to a given degree sequence (2016)
Journal Article
Golovach, P., & Mertzios, G. (2017). Graph editing to a given degree sequence. Theoretical Computer Science, 665, 1-12. https://doi.org/10.1016/j.tcs.2016.12.007

We investigate the parameterized complexity of the graph editing problem called Editing to a Graph with a Given Degree Sequence where the aim is to obtain a graph with a given degree sequence σ by at most k vertex deletions, edge deletions and edge a... Read More about Graph editing to a given degree sequence.

Online regenerator placement (2016)
Journal Article
Mertzios, G., Shalom, M., Wong, P., & Zaks, S. (2016). Online regenerator placement. Theory of Computing Systems, 61(3), 739-754. https://doi.org/10.1007/s00224-016-9711-3

Connections between nodes in optical networks are realized by lightpaths. Due to the decay of the signal, a regenerator has to be placed on every lightpath after at most d hops, for some given positive integer d. A regenerator can serve only one ligh... Read More about Online regenerator placement.

New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs (2016)
Journal Article
Giannopoulou, A., & Mertzios, G. (2016). New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs. SIAM Journal on Discrete Mathematics, 30(3), 1685-1725. https://doi.org/10.1137/15m1039468

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.

Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs (2016)
Conference Proceeding
Foucaud, F., Mertzios, G., Naserasr, R., Parreau, A., & Valicov, P. (2016). Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs. In E. W. Mayr (Ed.), Graph-theoretic concepts in computer science : 41st international workshop, WG 2015, Garching, Germany, June 17-19, 2015 ; revised papers (456-471). https://doi.org/10.1007/978-3-662-53174-7_32

We study the problems Locating-Dominating Set and Metric Dimension, which consist of determining a minimum-size set of vertices that distinguishes the vertices of a graph using either neighbourhoods or distances. We consider these problems when restr... Read More about Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs.

Stably computing order statistics with arithmetic population protocols (2016)
Conference Proceeding
Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2016). Stably computing order statistics with arithmetic population protocols. In P. Faliszewski, A. Muscholl, & R. Niedermeier (Eds.), 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) (68:1-68:14). https://doi.org/10.4230/lipics.mfcs.2016.68

In this paper we initiate the study of populations of agents with very limited capabilities that are globally able to compute order statistics of their arithmetic input values via pair-wise meetings. To this extent, we introduce the Arithmetic Popula... Read More about Stably computing order statistics with arithmetic population protocols.

The friendship problem on graphs (2016)
Journal Article
Mertzios, G., & Unger, W. (2016). The friendship problem on graphs. Journal of Multiple-Valued Logic and Soft Computing, 27(2-3), 275-285

In this paper we provide a purely combinatorial proof of the Friendship Theorem, which has been first proven by P. Erdős et al. by using also algebraic methods. Moreover, we generalize this theorem in a natural way, assuming that every pair of nodes... Read More about The friendship problem on graphs.

Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity (2016)
Journal Article
Foucaud, F., Mertzios, G., Naserasr, R., Parreau, A., & Valicov, P. (2016). Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity. Algorithmica, 78(3), 914-944. https://doi.org/10.1007/s00453-016-0184-1

We consider the problems of finding optimal identifying codes, (open) locating-dominating sets and resolving sets (denoted Identifying Code, (Open) Open Locating-Dominating Set and Metric Dimension) of an interval or a permutation graph. In these pro... Read More about Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity.

Determining majority in networks with local interactions and very small local memory (2016)
Journal Article
Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2017). Determining majority in networks with local interactions and very small local memory. Distributed Computing, 30(1), 1-16. https://doi.org/10.1007/s00446-016-0277-8

We study the problem of determining the majority type in an arbitrary connected network, each vertex of which has initially two possible types. The vertices may later change into other types, out of a set of a few additional possible types, and can i... Read More about Determining majority in networks with local interactions and very small local memory.

Graph editing to a given degree sequence (2016)
Conference Proceeding
Golovach, P., & Mertzios, G. (2016). Graph editing to a given degree sequence. In A. Kulikov, & G. Woeginger (Eds.), Computer science – Theory and applications : 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016. Proceedings (177-191). https://doi.org/10.1007/978-3-319-34171-2_13

We investigate the parameterized complexity of the graph editing problem called Editing to a Graph with a Given Degree Sequence where the aim is to obtain a graph with a given degree sequence σσ by at most k vertex or edge deletions and edge addition... Read More about Graph editing to a given degree sequence.

Intersection Graphs of L-Shapes and Segments in the Plane (2016)
Journal Article
Felsner, S., Knauer, K., Mertzios, G., & Ueckerdt, T. (2016). Intersection Graphs of L-Shapes and Segments in the Plane. Discrete Applied Mathematics, 206, 48-55. https://doi.org/10.1016/j.dam.2016.01.028

An L-shape is the union of a horizontal and a vertical segment with a common endpoint. These come in four rotations: Full-size image (25 K), Full-size image (25 K),Full-size image (25 K) and Full-size image (25 K). A k-bend path is a simple path in t... Read More about Intersection Graphs of L-Shapes and Segments in the Plane.

On temporally connected graphs of small cost (2016)
Conference Proceeding
Akrida, E., Gasieniec, L., Mertzios, G., & Spirakis, P. (2016). On temporally connected graphs of small cost. In Approximation and online algorithms : 13th International Workshop, WAOA 2015, Patras, Greece, September 17-18, 2015. Revised selected papers (84-96). https://doi.org/10.1007/978-3-319-28684-6_8

We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs of n vertices, where each edge has an associated set of discrete availability instances (labels). A journey from vertex u t... Read More about On temporally connected graphs of small cost.

Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs (2015)
Conference Proceeding
Giannopoulou, A., Mertzios, G., & Niedermeier, R. (2015). Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs. In T. Husfeldt, & I. Kanj (Eds.), 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) (102-113). https://doi.org/10.4230/lipics.ipec.2015.102

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)
Conference Proceeding
Giannopoulou, A., & Mertzios, G. (2015). New geometric representations and domination problems on tolerance and multitolerance graphs. In E. W. Mayr, & N. Ollinger (Eds.), 32nd international symposium on theoretical aspects of computer science (STACS 2015) (354-366). https://doi.org/10.4230/lipics.stacs.2015.354

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.

Intersection Graphs of L-Shapes and Segments in the Plane (2014)
Book Chapter
Felsner, S., Knauer, K., Mertzios, G., & Ueckerdt, T. (2014). Intersection Graphs of L-Shapes and Segments in the Plane. In E. Csuhaj-Varjú, M. Dietzfelbinger, & Z. Ésik (Eds.), Mathematical foundations of computer science 2014 : 39th international symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, part II (299-310). Springer Verlag. https://doi.org/10.1007/978-3-662-44465-8_26

An L-shape is the union of a horizontal and a vertical segment with a common endpoint. These come in four rotations: ⌊,⌈,⌋ and ⌉. A k-bend path is a simple path in the plane, whose direction changes k times from horizontal to vertical. If a graph adm... Read More about Intersection Graphs of L-Shapes and Segments in the Plane.

Determining Majority in Networks with Local Interactions and Very Small Local Memory (2014)
Book Chapter
Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2014). Determining Majority in Networks with Local Interactions and Very Small Local Memory. In J. Esparza, P. Fraigniaud, T. Husfeldt, & E. Koutsoupias (Eds.), Automata, languages, and programming : 41st international colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, proceedings, part I (871-882). Springer Verlag. https://doi.org/10.1007/978-3-662-43948-7_72

We study here the problem of determining the majority type in an arbitrary connected network, each vertex of which has initially two possible types (states). The vertices may have a few additional possible states and can interact in pairs only if the... Read More about Determining Majority in Networks with Local Interactions and Very Small Local Memory.

Minimum Bisection Is NP-hard on Unit Disk Graphs (2014)
Book Chapter
Díaz, J., & Mertzios, G. (2014). Minimum Bisection Is NP-hard on Unit Disk Graphs. In E. Csuhaj-Varjú, M. Dietzfelbinger, & Z. Ésik (Eds.), Mathematical foundations of computer science 2014 : 39th international symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, part II (251-262). Springer Verlag. https://doi.org/10.1007/978-3-662-44465-8_22

In this paper we prove that the Min-Bisection problem is NP-hard on unit disk graphs, thus solving a longstanding open question.

Approximating Fixation Probabilities in the Generalized Moran Process (2014)
Book Chapter
Mertzios, G. (2014). Approximating Fixation Probabilities in the Generalized Moran Process. In M. Kao (Ed.), Encyclopedia of algorithms (1-6). Springer Verlag. https://doi.org/10.1007/978-3-642-27848-8_596-1

Problem Definition Population and evolutionary dynamics have been extensively studied, usually with the assumption that the evolving population has no spatial structure. One of the main models in this area is the Moran process [17]. The initial popul... Read More about Approximating Fixation Probabilities in the Generalized Moran Process.

On the intersection of tolerance and cocomparability graphs (2014)
Journal Article
Mertzios, G., & Zaks, S. (2016). On the intersection of tolerance and cocomparability graphs. Discrete Applied Mathematics, 199, 46-88. https://doi.org/10.1016/j.dam.2014.10.025

Tolerance graphs have been extensively studied since their introduction, due to their interesting structure and their numerous applications, as they generalize both interval and permutation graphs in a natural way. It has been conjectured by Golumbic... Read More about On the intersection of tolerance and cocomparability graphs.

Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs (2014)
Journal Article
Mertzios, G., & Spirakis, P. (2016). Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs. Algorithmica, 74(1), 385-414. https://doi.org/10.1007/s00453-014-9949-6

The 3-coloring problem is well known to be NP-complete. It is also well known that it remains NP-complete when the input is restricted to graphs with diameter 4. Moreover, assuming the Exponential Time Hypothesis (ETH), 3-coloring cannot be solved in... Read More about Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs.

Ephemeral networks with random availability of links: diameter and connectivity (2014)
Conference Proceeding
Akrida, E., Gasieniec, L., Mertzios, G., & Spirakis, P. (2014). Ephemeral networks with random availability of links: diameter and connectivity. In Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures (267-276). https://doi.org/10.1145/2612669.2612693

In this work we consider temporal networks, the links of which are available only at random times (randomly available temporal networks). Our networks are {\em ephemeral}: their links appear sporadically, only at certain times, within a given maximum... Read More about Ephemeral networks with random availability of links: diameter and connectivity.

Approximating Fixation Probabilities in the Generalized Moran Process (2014)
Journal Article
Díaz, J., Goldberg, L., Mertzios, G., Richerby, D., Serna, M., & Spirakis, P. (2014). Approximating Fixation Probabilities in the Generalized Moran Process. Algorithmica, 69(1), 78-91. https://doi.org/10.1007/s00453-012-9722-7

We consider the Moran process, as generalized by Lieberman et al. (Nature 433:312–316, 2005). A population resides on the vertices of a finite, connected, undirected graph and, at each time step, an individual is chosen at random with probability pro... Read More about Approximating Fixation Probabilities in the Generalized Moran Process.

Computing and counting longest paths on circular-arc graphs in polynomial time (2014)
Journal Article
Mertzios, G., & Bezáková, I. (2014). Computing and counting longest paths on circular-arc graphs in polynomial time. Discrete Applied Mathematics, 164(Part 2), 383-399. https://doi.org/10.1016/j.dam.2012.08.024

The longest path problem asks for a path with the largest number of vertices in a given graph. In contrast to the Hamiltonian path problem, until recently polynomial algorithms for the longest path problem were known only for small graph classes, suc... Read More about Computing and counting longest paths on circular-arc graphs in polynomial time.

Parameterized Domination in Circle Graphs (2014)
Journal Article
Bousquet, N., Gonçalves, D., Mertzios, G., Paul, C., Sau, I., & Thomassé, S. (2014). Parameterized Domination in Circle Graphs. Theory of Computing Systems, 54(1), 45-72. https://doi.org/10.1007/s00224-013-9478-8

A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Appl. Math., 42(1):51–63, 1993] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-complete in circle graphs. To the best of ou... Read More about Parameterized Domination in Circle Graphs.

On the Recognition of Four-Directional Orthogonal Ray Graphs (2013)
Book Chapter
Felsner, S., Mertzios, G., & Mustata, I. (2013). On the Recognition of Four-Directional Orthogonal Ray Graphs. In K. Chatterjee, & J. Sgall (Eds.), Mathematical foundations of computer science 2013 : 38th international symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings (373-384). Springer Verlag. https://doi.org/10.1007/978-3-642-40313-2_34

Orthogonal ray graphs are the intersection graphs of horizontal and vertical rays (i.e. half-lines) in the plane. If the rays can have any possible orientation (left/right/up/down) then the graph is a 4-directional orthogonal ray graph (4-DORG). Othe... Read More about On the Recognition of Four-Directional Orthogonal Ray Graphs.

Temporal Network Optimization Subject to Connectivity Constraints (2013)
Book Chapter
Mertzios, G., Michail, O., Chatzigiannakis, I., & Spirakis, P. (2013). Temporal Network Optimization Subject to Connectivity Constraints. In F. V. Fomin, R. Freivalds, M. Kwiatkowska, & D. Peleg (Eds.), Automata, languages, and programming : 40th international colloquium, ICALP 2013, Riga, Latvia, July 8 - 12, 2013, proceedings, part II (657-668). Springer Verlag. https://doi.org/10.1007/978-3-642-39212-2_57

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.

Strong Bounds for Evolution in Networks (2013)
Book Chapter
Mertzios, G., & Spirakis, P. (2013). Strong Bounds for Evolution in Networks. In F. V. Fomin, R. Freivalds, M. Kwiatkowska, & D. Peleg (Eds.), Automata, languages, and programming : 40th international colloquium, ICALP 2013, Riga, Latvia, July 8 - 12, 2013, proceedings, part II (669-680). Springer Verlag. https://doi.org/10.1007/978-3-642-39212-2_58

This work extends what is known so far for a basic model of evolutionary antagonism in undirected networks (graphs). More specifically, this work studies the generalized Moran process, as introduced by Lieberman, Hauert, and Nowak [Nature, 433:312-31... Read More about Strong Bounds for Evolution in Networks.

Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs (2013)
Book Chapter
Mertzios, G., & Spirakis, P. (2013). Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs. In P. V. E. Boas, F. C. Groen, G. F. Italiano, J. Nawrocki, & H. Sack (Eds.), SOFSEM 2013 : theory and practice of computer science : 39th international conference on current trends in theory and practice of computer science, Špindlerův Mlýn, Czech Republic, January 26-31, 2013. Proceedings (332-343). Springer Verlag. https://doi.org/10.1007/978-3-642-35843-2_29

The 3-coloring problem is well known to be NP-complete. It is also well known that it remains NP-complete when the input is restricted to graphs with diameter 4. Moreover, assuming the Exponential Time Hypothesis (ETH), 3-coloring can not be solved i... Read More about Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs.

The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial (2013)
Book Chapter
Mertzios, G. (2013). The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial. In H. L. Bodlaender, & G. F. Italiano (Eds.), Algorithms - ESA 2013 : 21st annual European symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings (719-730). Springer Verlag. https://doi.org/10.1007/978-3-642-40450-4_61

Intersection graphs of geometric objects have been extensively studied, both due to 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.

On the fixation probability of superstars (2013)
Journal Article
Díaz, J., Goldberg, L., Mertzios, G., Richerby, D., Serna, M., & Spirakis, P. (2013). On the fixation probability of superstars. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 469(2156), https://doi.org/10.1098/rspa.2013.0193

The Moran process models the spread of genetic mutations through populations. A mutant with relative fitness r is introduced and the system evolves, either reaching fixation (an all-mutant population) or extinction (no mutants). In a widely cited pap... Read More about On the fixation probability of superstars.

Natural models for evolution on networks (2013)
Journal Article
Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2013). Natural models for evolution on networks. Theoretical Computer Science, 477, 76-95. https://doi.org/10.1016/j.tcs.2012.11.032

Evolutionary dynamics has been traditionally studied in the context of homogeneous populations, mainly described by the Moran process [P. Moran, Random processes in genetics, Proceedings of the Cambridge Philosophical Society 54 (1) (1958) 60–71]. Re... Read More about Natural models for evolution on networks.

An Intersection Model for Multitolerance Graphs: Efficient Algorithms and Hierarchy (2013)
Journal Article
Mertzios, G. (2014). An Intersection Model for Multitolerance Graphs: Efficient Algorithms and Hierarchy. Algorithmica, 69(3), 540-581. https://doi.org/10.1007/s00453-012-9743-2

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 has attracted many research efforts, mainly due to its interesting structure and its numer... Read More about An Intersection Model for Multitolerance Graphs: Efficient Algorithms and Hierarchy.

Placing regenerators in optical networks to satisfy multiple sets of requests (2012)
Journal Article
Mertzios, G., Sau, I., Shalom, M., & Zaks, S. (2012). Placing regenerators in optical networks to satisfy multiple sets of requests. IEEE/ACM Transactions on Networking, 20(6), 1870-1879. https://doi.org/10.1109/tnet.2012.2186462

The placement of regenerators in optical networks has become an active area of research during the last few 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... Read More about Placing regenerators in optical networks to satisfy multiple sets of requests.

Approximating Fixation Probabilities in the Generalized Moran Process (2012)
Conference Proceeding
Díaz, J., Goldberg, L., Mertzios, G., Richerby, D., Serna, M., & Spirakis, P. (2012). Approximating Fixation Probabilities in the Generalized Moran Process. In Y. Rabani (Ed.), Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, Kyoto, Japan, January 17-19, 2012 (954-960). https://doi.org/10.1137/1.9781611973099.76

We consider the Moran process, as generalized by Lieberman, Hauert and Nowak (Nature, 433:312--316, 2005). A population resides on the vertices of a finite, connected, undirected graph and, at each time step, an individual is chosen at random with pr... Read More about Approximating Fixation Probabilities in the Generalized Moran Process.

A simple polynomial algorithm for the longest path problem on cocomparability graphs (2012)
Journal Article
Mertzios, G., & Corneil, D. (2012). A simple polynomial algorithm for the longest path problem on cocomparability graphs. SIAM Journal on Discrete Mathematics, 26(3), 940-963. https://doi.org/10.1137/100793529

Given a graph $G$, the longest path problem asks to compute a simple path of $G$ with the largest number of vertices. This problem is the most natural optimization version of the well-known and well-studied Hamiltonian path problem, and thus it is NP... Read More about A simple polynomial algorithm for the longest path problem on cocomparability graphs.

Parameterized Domination in Circle Graphs (2012)
Conference Proceeding
Bousquet, N., Gonçalves, D., Mertzios, G., Paul, C., Sau, I., & Thomassé, S. (2012). Parameterized Domination in Circle Graphs. In M. C. .. Golumbic, M. Stern, A. Levy, & G. Morgenstern (Eds.), Graph-theoretic concepts in computer science : 38th International Workshop, WG 2012, Jerusalem, Israel, June 26-28, 2012 ; revised selected papers (308-319). https://doi.org/10.1007/978-3-642-34611-8_31

A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Applied Mathematics, 42(1):51-63, 1993] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-complete in circle graphs. To the be... Read More about Parameterized Domination in Circle Graphs.

The recognition of triangle graphs (2012)
Journal Article
Mertzios, G. (2012). The recognition of triangle graphs. Theoretical Computer Science, 438, 34-47. https://doi.org/10.1016/j.tcs.2012.02.042

Trapezoid graphs are the intersection graphs of trapezoids, where every trapezoid has a pair of opposite sides lying on two parallel lines L1 and L2 of the plane. This subclass of perfect graphs has received considerable attention as it generalizes i... Read More about The recognition of triangle graphs.

Optimizing busy time on parallel machines (2012)
Conference Proceeding
Mertzios, G., Shalom, M., Voloshin, A., Wong, P., & Zaks, S. (2012). Optimizing busy time on parallel machines. In Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium (IPDPS 2012) (238-248). https://doi.org/10.1109/ipdps.2012.31

We consider the following fundamental 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 simultaneously by a single... Read More about Optimizing busy time on parallel machines.

Online Regenerator Placement (2011)
Conference Proceeding
Mertzios, G., Shalom, M., Wong, P., & Zaks, S. (2011). Online Regenerator Placement. In A. Fernàndez Anta, G. Lipari, & M. Roy (Eds.), Principles of distributed systems, OPODIS 2011, 15th International Conference, 13-16 December 2011, Toulouse, France ; proceedings (4-17). https://doi.org/10.1007/978-3-642-25873-2_2

Connections between nodes in optical networks are realized by lightpaths. Due to the decay of the signal, a regenerator has to be placed on every lightpath after at most d hops, for some given positive integer d. A regenerator can serve only one ligh... Read More about Online Regenerator Placement.

Natural Models for Evolution on Networks (2011)
Conference Proceeding
Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2011). Natural Models for Evolution on Networks. In N. Chen, E. Elkind, & E. Koutsoupias (Eds.), Internet and network economics : 7th international workshop, WINE 2011, 11-14 December 2011 ; proceedings (290-301). https://doi.org/10.1007/978-3-642-25510-6_25

Evolutionary dynamics have been traditionally studied in the context of homogeneous populations, mainly described by the Moran process [15]. Recently, this approach has been generalized in [13] by arranging individuals on the nodes of a network (in g... Read More about Natural Models for Evolution on Networks.

The longest path problem has a polynomial solution on interval graphs (2011)
Journal Article
Ioannidou, K., Mertzios, G., & Nikolopoulos, S. (2011). The longest path problem has a polynomial solution on interval graphs. Algorithmica, 61(2), 320-341. https://doi.org/10.1007/s00453-010-9411-3

The longest path problem is the problem of finding a path of maximum length in a graph. Polynomial solutions for this problem are known only for small classes of graphs, while it is NP-hard on general graphs, as it is a generalization of the Hamilton... Read More about The longest path problem has a polynomial solution on interval graphs.

The recognition of tolerance and bounded tolerance graphs (2011)
Journal Article
Mertzios, G., Sau, I., & Zaks, S. (2011). The recognition of tolerance and bounded tolerance graphs. SIAM Journal on Computing, 40(5), 1234-1257. https://doi.org/10.1137/090780328

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.

Computing and Counting Longest Paths on Circular-Arc Graphs in Polynomial Time (2011)
Conference Proceeding
Mertzios, G., & Bezáková, I. (2011). Computing and Counting Longest Paths on Circular-Arc Graphs in Polynomial Time. In F. Bonomo, T. Liebling, J. Marenco, J. Szwarcfiter, & M. Valencia-Pabon (Eds.), . https://doi.org/10.1016/j.endm.2011.05.038

The longest path problem asks for a path with the largest number of vertices in a given graph. The first polynomial time algorithm (with running time O(n4)) has been recently developed for interval graphs. Even though interval and circular-arc graphs... Read More about Computing and Counting Longest Paths on Circular-Arc Graphs in Polynomial Time.

Vertex Splitting and the Recognition of Trapezoid Graphs (2011)
Journal Article
Mertzios, G., & Corneil, D. (2011). Vertex Splitting and the Recognition of Trapezoid Graphs. Discrete Applied Mathematics, 159(11), 1131-1147. https://doi.org/10.1016/j.dam.2011.03.023

Trapezoid graphs are the intersection family of trapezoids where every trapezoid has a pair of opposite sides lying on two parallel lines. These graphs have received considerable attention and lie strictly between permutation graphs (where the trapez... Read More about Vertex Splitting and the Recognition of Trapezoid Graphs.

An intersection model for multitolerance graphs: Efficient algorithms and hierarchy (2011)
Conference Proceeding
Mertzios, G. (2011). An intersection model for multitolerance graphs: Efficient algorithms and hierarchy. In Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 23-25 January 2011, San Francisco ; proceedings (1306-1317)

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in con ict. This class of graphs has attracted many research eorts, mainly due to its interesting structure and its numerous... Read More about An intersection model for multitolerance graphs: Efficient algorithms and hierarchy.

The Recognition of Triangle Graphs (2011)
Conference Proceeding
Mertzios, G. (2011). The Recognition of Triangle Graphs. In T. Schwentick, & C. Dürr (Eds.), 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, 10-12 March 2011, Dortmund, Germany ; proceedings (591-602). https://doi.org/10.4230/lipics.stacs.2011.591

Trapezoid graphs are the intersection graphs of trapezoids, where every trapezoid has a pair of opposite sides lying on two parallel lines L_{1} and L_{2} of the plane. Strictly between permutation and trapezoid graphs lie the simple-triangle graphs... Read More about The Recognition of Triangle Graphs.

On the intersection of tolerance and cocomparability graphs (2010)
Conference Proceeding
Mertzios, G., & Zaks, S. (2010). On the intersection of tolerance and cocomparability graphs. In O. Cheong, K. Chwa, & K. Park (Eds.), Algorithms and Computation, 21st International Symposium, ISAAC 2010, 15-17 December 2010, Jeju Island, Korea ; proceedings Part I (230-240). https://doi.org/10.1007/978-3-642-17517-6_22

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)
Conference Proceeding
Mertzios, G., Sau, I., Shalom, M., & Zaks, S. (2010). Placing regenerators in optical networks to satisfy multiple sets of requests. In S. Abramsky, C. Gavoille, C. Kirchner, F. Meyer auf der Heide, & P. G. Spirakis (Eds.), Automata, Languages and Programming : 37th International Colloquium, ICALP 2010, 6-10 July 2010, Bordeaux, France ; proceedings, Part II (333-344). https://doi.org/10.1007/978-3-642-14162-1_28

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)
Conference Proceeding
Mertzios, G., Sau, I., & Zaks, S. (2010). A new intersection model and improved algorithms for tolerance graphs. In C. Paul, & M. Habib (Eds.), Graph-theoretic concepts in computer science : 35th international workshop, WG 2009, 24-26 June 2009, Montpellier, France ; revised papers (285-295). https://doi.org/10.1007/978-3-642-11409-0_25

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)
Conference Proceeding
Mertzios, G., Sau, I., & Zaks, S. (2010). The Recognition of Tolerance and Bounded Tolerance Graphs. In J. Marion, & T. Schwentick (Eds.), . https://doi.org/10.4230/lipics.stacs.2010.2487

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.

A New Intersection Model and Improved Algorithms for Tolerance Graphs (2009)
Journal Article
Mertzios, G., Sau, I., & Zaks, S. (2010). A New Intersection Model and Improved Algorithms for Tolerance Graphs. SIAM Journal on Discrete Mathematics, 23(4), 1800-1813. https://doi.org/10.1137/09075994x

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.

New PDE-based methods for image enhancement using SOM and Bayesian inference in various discretization schemes (2009)
Journal Article
Karras, D., & Mertzios, G. (2009). New PDE-based methods for image enhancement using SOM and Bayesian inference in various discretization schemes. Measurement Science and Technology, 20(10), Article 104012. https://doi.org/10.1088/0957-0233/20/10/104012

A novel approach is presented in this paper for improving anisotropic diffusion PDE models, based on the Perona–Malik equation. A solution is proposed from an engineering perspective to adaptively estimate the parameters of the regularizing function... Read More about New PDE-based methods for image enhancement using SOM and Bayesian inference in various discretization schemes.

The longest path problem is polynomial on interval graphs (2009)
Conference Proceeding
Ioannidou, K., Mertzios, G., & Nikolopoulos, S. (2009). The longest path problem is polynomial on interval graphs. In K. Rastislav, & N. Damian (Eds.), Mathematical foundations of computer science 2009 34th international symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009 : proceedings (403-414). https://doi.org/10.1007/978-3-642-03816-7_35

The longest path problem is the problem of finding a path of maximum length in a graph. Polynomial solutions for this problem are known only for small classes of graphs, while it is NP-hard on general graphs, as it is a generalization of the Hamilton... Read More about The longest path problem is polynomial on interval graphs.

A parameterized algorithm for the preemptive scheduling of equal-length jobs (2009)
Conference Proceeding
Mertzios, G., & Unger, W. (2009). A parameterized algorithm for the preemptive scheduling of equal-length jobs.

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 n i=1 wiCi of the jobs. We propose for this problem... Read More about A parameterized algorithm for the preemptive scheduling of equal-length jobs.

A matrix characterization of interval and proper interval graphs (2008)
Journal Article
Mertzios, G. (2008). A matrix characterization of interval and proper interval graphs. Applied Mathematics Letters, 21(4), 332-337. https://doi.org/10.1016/j.aml.2007.04.001

In this work a matrix representation that characterizes the interval and proper interval graphs is presented, which is useful for the efficient formulation and solution of optimization problems, such as the k-cluster problem. For the construction of... Read More about A matrix characterization of interval and proper interval graphs.

Solution of parameter-varying linear matrix inequalities in Toeplitz form (2006)
Journal Article
Mertzios, G. (2006). Solution of parameter-varying linear matrix inequalities in Toeplitz form. Journal of applied functional analysis, 1(2), 131-152

In this paper the necessary and sufficient conditions are given for the solution of a system of parameter varying linear inequalities of the form A (t) x ≥ b (t) for all t ∈ T ,where T is an arbitrary set, x is the unknown vector, A (t) is a known tria... Read More about Solution of parameter-varying linear matrix inequalities in Toeplitz form.

A sensitive optical polarimetric imaging technique for surface defects detection of aircraft turbine engines (2004)
Journal Article
Giakos, G., Fraiwan, L., Patnekar, N., Sumrain, S., Mertzios, G., & Periyathamby, S. (2004). A sensitive optical polarimetric imaging technique for surface defects detection of aircraft turbine engines. IEEE Transactions on Instrumentation and Measurement, 53(1), 216-222. https://doi.org/10.1109/tim.2003.821497

The design of an optical polarimetric imaging system, aimed to detect cracks or structural defects on the surface of rotating aircraft engine shafts, is presented: The experimental results, clearly indicate that high. signal-to-noise ratio signals ca... Read More about A sensitive optical polarimetric imaging technique for surface defects detection of aircraft turbine engines.

Discretization schemes and numerical approximations of PDE impainting models and a comparative evaluation on novel real world MRI reconstruction applications (2004)
Conference Proceeding
Karras, D., & Mertzios, G. (2004). Discretization schemes and numerical approximations of PDE impainting models and a comparative evaluation on novel real world MRI reconstruction applications. In 2004 IEEE International Workshop on Imaging Systems and Techniques (IST) : 14 May 2004, Stresa, Italy ; proceedings (153-158). https://doi.org/10.1109/ist.2004.1397304

While various PDE models are in discussion since the last ten years and are widely applied nowadays in image processing and computer vision tasks, including restoration, filtering, segmentation and object tracking, the perspective adopted in the majo... Read More about Discretization schemes and numerical approximations of PDE impainting models and a comparative evaluation on novel real world MRI reconstruction applications.

A novel multipath dispersion reduction technique based on controlled-polarization optical wireless link set-up (2003)
Conference Proceeding
Giakos, G., Patnekar, N., Sumrain, S., Fraiwan, L., Kumar, V., & Mertzios, G. (2003). A novel multipath dispersion reduction technique based on controlled-polarization optical wireless link set-up. In Instrumentation and Measurement Technology, 20th Annual Conference, IMTC '03, 20-22 May 2003, Colorado, USA ; proceedings (1622-1626). https://doi.org/10.1109/imtc.2003.1208024

The detection characteristics of an indoor-optical communication system, which utilizes infrared radiation as carrier has been explored and enhanced for telemedicine, and wireless local area network applications. The novelty of the presented techniqu... Read More about A novel multipath dispersion reduction technique based on controlled-polarization optical wireless link set-up.