All Outputs (4)

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.

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.

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.