Outputs (47)

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.

Editing to a Planar Graph of Given Degrees (2016)
Journal Article
Dabrowski, K., Golovach, P., van 't Hof, P., Paulusma, D., & Thilikos, D. (2016). Editing to a Planar Graph of Given Degrees. Journal of Computer and System Sciences, 85, 168-182. https://doi.org/10.1016/j.jcss.2016.11.009

We consider the following graph modification problem. Let the input consist of a graph G=(V,E), a weight function w:V∪E→N, a cost function c:V∪E→N0 and a degree function δ:V→N0, together with three integers kv,ke and C . The question is whether we ca... Read More about Editing to a Planar Graph of Given Degrees.

Squares of low clique number (2016)
Presentation / Conference Contribution
Golovach, P., Kratsch, D., Paulusma, D., & Stewart, A. Squares of low clique number. Presented at 14th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW16), Gargnano, Italy

The Square Root problem is that of deciding whether a given graph admits a square root. This problem is only known to be NP-complete for chordal graphs and polynomial-time solvable for non-trivial minor-closed graph classes and a very limited number... Read More about Squares of low clique number.

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.

The price of connectivity for feedback vertex set (2016)
Journal Article
Belmonte, R., van ’t Hof, P., Kamiński, M., & Paulusma, D. (2017). The price of connectivity for feedback vertex set. Discrete Applied Mathematics, 217(Part B), 132-143. https://doi.org/10.1016/j.dam.2016.08.011

Let View the MathML source and View the MathML source denote the cardinalities of a minimum feedback vertex set and a minimum connected feedback vertex set of a graph G, respectively. The price of connectivity for feedback vertex set (poc-fvs) for a... Read More about The price of connectivity for feedback vertex set.

Reducing the clique and chromatic number via edge contractions and vertex deletions (2016)
Presentation / Conference Contribution
Paulusma, D., Picouleau, C., & Ries, B. (2016, May). Reducing the clique and chromatic number via edge contractions and vertex deletions. Presented at 4th International Symposium on Combinatorial Optimization (ISCO 2016), Vietri sul Mare, Italy

We consider the following problem: can a certain graph parameter of some given graph G be reduced by at least d, for some integer d, via at most k graph operations from some specified set S, for some given integer k? As graph parameters we take the c... Read More about Reducing the clique and chromatic number via edge contractions and vertex deletions.

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.

Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing (2016)
Presentation / Conference Contribution
Berenbrink, P., Friedetzky, T., Kling, P., Mallmann-Trenn, F., & Wastell, C. (2016, August). Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing. Presented at 24th Annual European Symposium on Algorithms (ESA 2016), Aarhus, Denmark

We consider plurality consensus in networks of n nodes. Initially, each node has one of k opinions. The nodes execute a (randomized) distributed protocol to agree on the plurality opinion (the opinion initially supported by the most nodes). In certai... Read More about Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing.

Well-quasi-ordering versus clique-width: new results on bigenic classes (2016)
Presentation / Conference Contribution
Dabrowski, K. K., Lozin, V. V., & Paulusma, D. (2016, August). Well-quasi-ordering versus clique-width: new results on bigenic classes. Presented at 27th International Workshop on Combinatorial Algorithms (IWOCA 2016)., Helsinki, Finland

Daligault, Rao and Thomassé conjectured that if a hereditary class of graphs is well-quasi-ordered by the induced subgraph relation then it has bounded clique-width. Lozin, Razgon and Zamaraev recently showed that this conjecture is not true for infi... Read More about Well-quasi-ordering versus clique-width: new results on bigenic classes.

Finding cactus roots in polynomial time (2016)
Presentation / Conference Contribution
Golovach, P. A., Kratsch, D., Paulusma, D., & Stewart, A. (2016, August). Finding cactus roots in polynomial time. Presented at 27th International Workshop on Combinatorial Algorithms (IWOCA 2016)., Helsinki, Finland

A cactus is a connected graph in which each edge belongs to at most one cycle. A graph H is a cactus root of a graph G if H is a cactus and G can be obtained from H by adding an edge between any two vertices in H that are of distance 2 in H. We show... Read More about Finding cactus roots in polynomial time.

Minimal Disconnected Cuts in Planar Graphs (2016)
Journal Article
Kamiński, M., Paulusma, D., Stewart, A., & Thilikos, D. (2016). Minimal Disconnected Cuts in Planar Graphs. Networks, 68(4), 250-259. https://doi.org/10.1002/net.21696

The problem of finding a disconnected cut in a graph is NP-hard in general but polynomial-time solvable on planar graphs. The problem of finding a minimal disconnected cut is also NP-hard but its computational complexity was not known for planar grap... Read More about Minimal Disconnected Cuts in Planar Graphs.

Lengths of words in transformation semigroups generated by digraphs (2016)
Journal Article
Cameron, P. J., Castillo-Ramirez, A., Gadouleau, M., & Mitchell, J. D. (2017). Lengths of words in transformation semigroups generated by digraphs. Journal of Algebraic Combinatorics, 45(1), 149-170. https://doi.org/10.1007/s10801-016-0703-9

Given a simple digraph D on n vertices (with n≥2n≥2 ), there is a natural construction of a semigroup of transformations ⟨D⟩⟨D⟩ . For any edge (a, b) of D, let a→ba→b be the idempotent of rank n−1n−1 mapping a to b and fixing all vertices other than... Read More about Lengths of words in transformation semigroups generated by digraphs.

Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs (2016)
Presentation / Conference Contribution
Foucaud, F., Mertzios, G., Naserasr, R., Parreau, A., & Valicov, P. (2016, August). Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs. Presented at 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Munich, Germany

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.

Open problems on graph coloring for special graph classes (2016)
Presentation / Conference Contribution
Paulusma, D. (2015, June). Open problems on graph coloring for special graph classes. Presented at 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015), Munich, Germany

For a given graph G and integer k, the Coloring problem is that of testing whether G has a k-coloring, that is, whether there exists a vertex mapping c:V→{1,2,…}c:V→{1,2,…} such that c(u)≠c(v)c(u)≠c(v) for every edge uv∈Euv∈E. We survey known results... Read More about Open problems on graph coloring for special graph classes.

The stable fixtures problem with payments (2016)
Presentation / Conference Contribution
Biró, P., Kern, W., Paulusma, D., & Wojuteczky, P. (2015, June). The stable fixtures problem with payments. Presented at 41 International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015), Munich, Germany

We generalize two well-known game-theoretic models by introducing multiple partners matching games, defined by a graph G=(N,E)G=(N,E), with an integer vertex capacity function b and an edge weighting w. The set N consists of a number of players that... Read More about The stable fixtures problem with payments.

Using contracted solution graphs for solving reconfiguration problems (2016)
Presentation / Conference Contribution
Bonsma, P., & Paulusma, D. (2016, August). Using contracted solution graphs for solving reconfiguration problems. Presented at 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), Krakow, Poland

We introduce a dynamic programming method for solving reconfiguration problems, based on contracted solution graphs, which are obtained from solution graphs by performing an appropriate series of edge contractions that decrease the graph size without... Read More about Using contracted solution graphs for solving reconfiguration problems.

Stably computing order statistics with arithmetic population protocols (2016)
Presentation / Conference Contribution
Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2016, August). Stably computing order statistics with arithmetic population protocols. Presented at 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)., Krakow, Poland

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.

Constraint Satisfaction Problems for Reducts of Homogeneous Graphs (2016)
Presentation / Conference Contribution
Bodirsky, M., Martin, B., Pinsker, M., & Pongrácz, A. (2016, July). Constraint Satisfaction Problems for Reducts of Homogeneous Graphs. Presented at 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, Rome, Italy

For n >= 3, let (Hn, E) denote the n-th Henson graph, i.e., the unique countable homogeneous graph with exactly those finite graphs as induced subgraphs that do not embed the complete graph on n vertices. We show that for all structures Gamma with do... Read More about Constraint Satisfaction Problems for Reducts of Homogeneous Graphs.

Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time (2016)
Presentation / Conference Contribution
Berenbrink, P., Friedetzky, T., Giakkoupis, G., & Kling, P. (2016, August). Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time. Presented at 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Rome, Italy

Plurality consensus considers a network of n nodes, each having one of k opinions. Nodes execute a (randomized) distributed protocol with the goal that all nodes adopt the plurality (the opinion initially supported by the most nodes). Communication i... Read More about Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time.