GM
George B. Mertzios
cs.DScs.DMcs.CCmath.COcs.CEcs.DCmath.PRq-bio.PEAPX-hardcs.NI
On Valency
published · living versionsW_dqvfa3vp·v1 · currentpublished
Recognizing Label-Connected Graphs
with Ralf Klasing, Hendrik Molter, Nils Morawietz, Paul G. Spirakis
1 version
Preprints & journals
56 papers in the corpus · 2005–2026Enumerating Inclusion-Maximal Arithmetic Progressions2606.11067v1 · Brian Bemman, Maximilien Gadouleau, Oliver W. Gnilke et al.2026 · 0 citationsarXiv
Round-Delayed Amnesiac Flooding2604.04260v1 · Oluwatobi Alafin, George B. Mertzios, Paul G. Spirakis2026 · 0 citationsarXiv
Sharp Thresholds for Temporal Motifs and Doubling Time in Random Temporal Graphs2602.01847v3 · Henry Austin, George B. Mertzios, Paul G. Spirakis2026 · 0 citationsarXiv
Maintaining Bipartite Colourings on Temporal Graphs on a Budget2511.20338v1 · Duncan Adamson, George B. Mertzios, Paul G. Spirakis2025 · 0 citationsarXiv
Temporal Graph Realization With Bounded Stretch2504.14258v1 · George B. Mertzios, Hendrik Molter, Nils Morawietz et al.2025 · 0 citationsarXiv
NP-Completeness of the Combinatorial Distance Matrix Realisation Problem2406.14729v1 · David L. Fairbairn, George B. Mertzios, Norbert Peyerimhoff2024 · 0 citationsarXiv
On the existence of -temporal cliques in random simple temporal graphs2404.07147v1 · George B. Mertzios, Sotiris Nikoletseas, Christoforos Raptopoulos et al.2024 · 0 citationsarXiv
Realizing temporal transportation trees2403.18513v3 · George B. Mertzios, Hendrik Molter, Nils Morawietz et al.2024 · 1 citationarXiv
Payment Scheduling in the Interval Debt Model2403.02198v2 · Tom Friedetzky, David C. Kutner, George B. Mertzios et al.2024 · 4 citationsarXiv
Graphs with minimum fractional domatic number2302.11668v2 · Maximilien Gadouleau, Nathaniel Harms, George B. Mertzios et al.2023 · 0 citationsarXiv
Realizing temporal graphs from fastest travel times2302.08860v4 · Nina Klobas, George B. Mertzios, Hendrik Molter et al.2023 · 1 citationarXiv
The Complexity of Temporal Vertex Cover in Small-Degree Graphs2204.04832v2 · Thekla Hamm, Nina Klobas, George B. Mertzios et al.2022 · 15 citationsarXiv
The complexity of computing optimum labelings for temporal connectivity2202.05880v2 · Nina Klobas, George B. Mertzios, Hendrik Molter et al.2022 · 7 citationsarXiv
The Complexity of Growing a Graph2107.14126v5 · George B. Mertzios, Othon Michail, George Skretas et al.2021 · 5 citationsarXiv
Interference-free Walks in Time: Temporally Disjoint Paths2105.08335v2 · Nina Klobas, George B. Mertzios, Hendrik Molter et al.2021 · 15 citationsarXiv
The Complexity of Transitively Orienting Temporal Graphs2102.06783v3 · George B. Mertzios, Hendrik Molter, Malte Renken et al.2021 · 4 citationsarXiv
Equitable Scheduling on a Single Machine2010.04643v2 · Klaus Heeger, Danny Hermelin, George B. Mertzios et al.2020 · 11 citationsarXiv
Matching in Stochastically Evolving Graphs2005.08263v1 · Eleni C. Akrida, Argyrios Deligkas, George B. Mertzios et al.2020 · 1 citationarXiv
Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle2004.06036v2 · Argyrios Deligkas, George B. Mertzios, Paul G. Spirakis et al.2020 · 0 citationsarXiv
Linear Programming Complementation1907.12775v2 · Maximilien Gadouleau, George B. Mertzios, Viktor Zamaraev2019 · 0 citationsarXiv
Computing Maximum Matchings in Temporal Graphs1905.05304v6 · George B. Mertzios, Hendrik Molter, Rolf Niedermeier et al.2019 · 23 citationsarXiv
How fast can we reach a target vertex in stochastic temporal graphs?1903.03636v1 · Eleni C. Akrida, George B. Mertzios, Sotiris Nikoletseas et al.2019 · 21 citationsarXiv
Sliding Window Temporal Graph Coloring1811.04753v2 · George B. Mertzios, Hendrik Molter, Viktor Zamaraev2018 · 26 citationsarXiv
Deleting edges to restrict the size of an epidemic in temporal networks1805.06836v2 · Jessica Enright, Kitty Meeks, George B. Mertzios et al.2018 · 64 citationsarXiv
The temporal explorer who returns to the base1805.04713v1 · Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis2018 · 38 citationsarXiv
Lower and Upper Bound for Computing the Size of All Second Neighbourhoods1805.01684v1 · Gregory Gutin, George B. Mertzios, Felix Reidl2018 · 0 citationsarXiv
Temporal Vertex Cover with a Sliding Time Window1802.07103v3 · Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis et al.2018 · 64 citationsarXiv
Searching for Maximum Out-Degree Vertices in Tournaments1801.04702v1 · Gregory Gutin, George B. Mertzios, Felix Reidl2018 · 3 citationsarXiv
Kernelization Lower Bounds for Finding Constant-Size Subgraphs1710.07601v2 · Till Fluschnik, George B. Mertzios, Andr'e Nichterlein2017 · 4 citationsarXiv
A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs1703.05598v3 · George B. Mertzios, Andr'e Nichterlein, Rolf Niedermeier2017 · 17 citationsarXiv
Binary Search in Graphs Revisited1702.08899v2 · Argyrios Deligkas, George B. Mertzios, Paul G. Spirakis2017 · 8 citationsarXiv
When can Graph Hyperbolicity be computed in Linear Time?1702.06503v1 · Till Fluschnik, Christian Komusiewicz, George B. Mertzios et al.2017 · 12 citationsarXiv
The Complexity of Optimal Design of Temporally Connected Graphs.32025196 · Akrida, Eleni C, Gąsieniec, Leszek, Mertzios, George B et al.2020 · 39 citationsTheory of computing systems. 2017;61(3):907-944
The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs1606.09000v5 · Ren'e van Bevern, Till Fluschnik, George B. Mertzios et al.2016 · 9 citationsDiscrete Optimzation 30:20-50, 2018
On the Complexity of Weighted Greedy Matchings1602.05909v2 · Argyrios Deligkas, George B. Mertzios, Paul G. Spirakis2016 · 0 citationsarXiv
Graph Editing to a Given Degree Sequence1601.03174v1 · Petr A. Golovach, George B. Mertzios2016 · 9 citationsarXiv
Identification, location-domination and metric dimension on interval and permutation graphs. I. Bounds1507.08164v2 · Florent Foucaud, George B. Mertzios, Reza Naserasr et al.2015 · 41 citationsTheoretical Computer Science 668:43-58 (2017)
Polynomial Fixed-Parameter Algorithms: A Case Study for Longest Path on Interval Graphs1506.01652v4 · Archontia C. Giannopoulou, George B. Mertzios, Rolf Niedermeier2015 · 43 citationsarXiv
Temporal Network Optimization Subject to Connectivity Constraints1502.04382v2 · George B. Mertzios, Othon Michail, Paul G. Spirakis2015 · 69 citationsarXiv
New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs1412.1543v2 · Archontia C. Giannopoulou, George B. Mertzios2014 · 4 citationsarXiv
Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity1405.2424v3 · Florent Foucaud, George B. Mertzios, Reza Naserasr et al.2014 · 51 citationsAlgorithmica 78(3):914-944 (2017)
Intersection Graphs of L-Shapes and Segments in the Plane1405.1476v2 · Stefan Felsner, Kolja Knauer, George B. Mertzios et al.2014 · 20 citationsarXiv
Determining Majority in Networks with Local Interactions and very Small Local Memory1404.7671v1 · George B. Mertzios, Sotiris E. Nikoletseas, Christoforos L. Raptopoulos et al.2014 · 54 citationsarXiv
Minimum Bisection is NP-hard on Unit Disk Graphs1404.0117v3 · Josep Diaz, George B. Mertzios2014 · 3 citationsarXiv
Online Regenerator Placement1309.0195v1 · George B. Mertzios, Mordechai Shalom, Prudence W.H. Wong et al.2013 · 0 citationsarXiv
Strong Bounds for Evolution in Undirected Graphs1211.2384v2 · George B. Mertzios, Paul G. Spirakis2012 · 2 citationsarXiv
The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial1210.4352v2 · George B. Mertzios2012 · 17 citationsarXiv
On the Intersection of Tolerance and Cocomparability Graphs1207.0552v1 · George B. Mertzios, Shmuel Zaks2012 · 3 citationsarXiv
Parameterized Domination in Circle Graphs1205.3728v1 · Nicolas Bousquet, Daniel Goncalves, George B. Mertzios et al.2012 · 11 citationsarXiv
Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs1202.4665v3 · George B. Mertzios, Paul G. Spirakis2012 · 11 citationsarXiv
Career total: 175 works. 56 are in this corpus.Showing the 50 most recent.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.