Skip to main content

Research Repository

Advanced Search

All Outputs (11)

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.

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 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.