43 citations · 187 across the 40 of their papers we have counts for
4 papers · 1 filter
Kernelization Lower Bounds for Finding Constant-Size Subgraphs
Till Fluschnik, George B. Mertzios, André Nichterlein
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 instan…
A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs
George B. Mertzios, André Nichterlein, Rolf Niedermeier
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 solvab…
When can Graph Hyperbolicity be computed in Linear Time?
Till Fluschnik, Christian Komusiewicz, George B. Mertzios +3
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 int…
Binary Search in Graphs Revisited
Argyrios Deligkas, George B. Mertzios, Paul G. Spirakis
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 bin…