Skip to main content

Research Repository

Advanced Search

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.