All Outputs (11)

Graph editing to a given degree sequence (2016)
Journal Article
Golovach, P., & Mertzios, G. (2017). Graph editing to a given degree sequence. Theoretical Computer Science, 665, 1-12. https://doi.org/10.1016/j.tcs.2016.12.007

We investigate the parameterized complexity of the graph editing problem called Editing to a Graph with a Given Degree Sequence where the aim is to obtain a graph with a given degree sequence σ by at most k vertex deletions, edge deletions and edge a... Read More about Graph editing to a given degree sequence.

Online regenerator placement (2016)
Journal Article
Mertzios, G., Shalom, M., Wong, P., & Zaks, S. (2016). Online regenerator placement. Theory of Computing Systems, 61(3), 739-754. https://doi.org/10.1007/s00224-016-9711-3

Connections between nodes in optical networks are realized by lightpaths. Due to the decay of the signal, a regenerator has to be placed on every lightpath after at most d hops, for some given positive integer d. A regenerator can serve only one ligh... Read More about Online regenerator placement.

New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs (2016)
Journal Article
Giannopoulou, A., & Mertzios, G. (2016). New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs. SIAM Journal on Discrete Mathematics, 30(3), 1685-1725. https://doi.org/10.1137/15m1039468

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain amount of overlap without being in conflict. In one of the most natural generalizations of tolerance graphs with direct applications in the comparison of DN... Read More about New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs.

Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs (2016)
Conference Proceeding
Foucaud, F., Mertzios, G., Naserasr, R., Parreau, A., & Valicov, P. (2016). Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs. In E. W. Mayr (Ed.), Graph-theoretic concepts in computer science : 41st international workshop, WG 2015, Garching, Germany, June 17-19, 2015 ; revised papers (456-471). https://doi.org/10.1007/978-3-662-53174-7_32

We study the problems Locating-Dominating Set and Metric Dimension, which consist of determining a minimum-size set of vertices that distinguishes the vertices of a graph using either neighbourhoods or distances. We consider these problems when restr... Read More about Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs.

Stably computing order statistics with arithmetic population protocols (2016)
Conference Proceeding
Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2016). Stably computing order statistics with arithmetic population protocols. In P. Faliszewski, A. Muscholl, & R. Niedermeier (Eds.), 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) (68:1-68:14). https://doi.org/10.4230/lipics.mfcs.2016.68

In this paper we initiate the study of populations of agents with very limited capabilities that are globally able to compute order statistics of their arithmetic input values via pair-wise meetings. To this extent, we introduce the Arithmetic Popula... Read More about Stably computing order statistics with arithmetic population protocols.

The friendship problem on graphs (2016)
Journal Article
Mertzios, G., & Unger, W. (2016). The friendship problem on graphs. Journal of Multiple-Valued Logic and Soft Computing, 27(2-3), 275-285

In this paper we provide a purely combinatorial proof of the Friendship Theorem, which has been first proven by P. Erdős et al. by using also algebraic methods. Moreover, we generalize this theorem in a natural way, assuming that every pair of nodes... Read More about The friendship problem on graphs.

Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity (2016)
Journal Article
Foucaud, F., Mertzios, G., Naserasr, R., Parreau, A., & Valicov, P. (2016). Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity. Algorithmica, 78(3), 914-944. https://doi.org/10.1007/s00453-016-0184-1

We consider the problems of finding optimal identifying codes, (open) locating-dominating sets and resolving sets (denoted Identifying Code, (Open) Open Locating-Dominating Set and Metric Dimension) of an interval or a permutation graph. In these pro... Read More about Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity.

Determining majority in networks with local interactions and very small local memory (2016)
Journal Article
Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2017). Determining majority in networks with local interactions and very small local memory. Distributed Computing, 30(1), 1-16. https://doi.org/10.1007/s00446-016-0277-8

We study the problem of determining the majority type in an arbitrary connected network, each vertex of which has initially two possible types. The vertices may later change into other types, out of a set of a few additional possible types, and can i... Read More about Determining majority in networks with local interactions and very small local memory.

Graph editing to a given degree sequence (2016)
Conference Proceeding
Golovach, P., & Mertzios, G. (2016). Graph editing to a given degree sequence. In A. Kulikov, & G. Woeginger (Eds.), Computer science – Theory and applications : 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016. Proceedings (177-191). https://doi.org/10.1007/978-3-319-34171-2_13

We investigate the parameterized complexity of the graph editing problem called Editing to a Graph with a Given Degree Sequence where the aim is to obtain a graph with a given degree sequence σσ by at most k vertex or edge deletions and edge addition... Read More about Graph editing to a given degree sequence.

Intersection Graphs of L-Shapes and Segments in the Plane (2016)
Journal Article
Felsner, S., Knauer, K., Mertzios, G., & Ueckerdt, T. (2016). Intersection Graphs of L-Shapes and Segments in the Plane. Discrete Applied Mathematics, 206, 48-55. https://doi.org/10.1016/j.dam.2016.01.028

An L-shape is the union of a horizontal and a vertical segment with a common endpoint. These come in four rotations: Full-size image (25 K), Full-size image (25 K),Full-size image (25 K) and Full-size image (25 K). A k-bend path is a simple path in t... Read More about Intersection Graphs of L-Shapes and Segments in the Plane.

On temporally connected graphs of small cost (2016)
Conference Proceeding
Akrida, E., Gasieniec, L., Mertzios, G., & Spirakis, P. (2016). On temporally connected graphs of small cost. In Approximation and online algorithms : 13th International Workshop, WAOA 2015, Patras, Greece, September 17-18, 2015. Revised selected papers (84-96). https://doi.org/10.1007/978-3-319-28684-6_8

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 On temporally connected graphs of small cost.