Skip to main content

Research Repository

Advanced Search

Outputs (9)

Binary search in graphs revisited (2017)
Presentation / Conference Contribution
Deligkas, A., Mertzios, G., & Spirakis, P. (2017, August). Binary search in graphs revisited. Presented at 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS), Aalborg, Denmark

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)
Presentation / Conference Contribution
Mertzios, G., Nichterlein, A., & Niedermeier, R. (2017, August). The Power of Linear-Time Data Reduction for Maximum Matching. Presented at 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS)., Aalborg, Denmark

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)
Presentation / Conference Contribution
Fluschnik, T., Komusiewicz, C., Mertzios, G., Nichterlein, A., Niedermeier, R., & Talmon, N. (2023, July). When can graph hyperbolicity be computed in linear time?. Presented at Algorithms and Data Structures Symposium (WADS) 2017, St. John’s, NL, Canada

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)
Presentation / Conference Contribution
Deligkas, A., Mertzios, G., & Spirakis, P. (2017, February). The computational complexity of weighted greedy matching. Presented at 31st AAAI Conference on Artificial Intelligence (AAAI-17), San Francisco, California, USA

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)
Presentation / Conference Contribution
Bevern, R., Fluschnik, T., Mertzios, G., Molter, H., Sorge, M., & Suchý, O. (2016, August). Finding secluded places of special interest in graphs. Presented at 11th International Symposium on Parameterized and Exact Computation (IPEC), Aarhus, Denmark

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.