All Outputs (7)

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.

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.

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.