ﻻ يوجد ملخص باللغة العربية
We introduce the rendezvous game with adversaries. In this game, two players, {sl Facilitator} and {sl Disruptor}, play against each other on a graph. Facilitator has two agents, and Disruptor has a team of $k$ agents located in some vertices of the graph. They take turns in moving their agents to adjacent vertices (or staying). Facilitator wins if his agents meet in some vertex of the graph. The goal of Disruptor is to prevent the rendezvous of Facilitators agents. Our interest is to decide whether Facilitator can win. It appears that, in general, the problem is PSPACE-hard and, when parameterized by $k$, co-W[2]-hard. Moreover, even the games variant where we ask whether Facilitator can ensure the meeting of his agents within $tau$ steps is co-NP-complete already for $tau=2$. On the other hand, for chordal and $P_5$-free graphs, we prove that the problem is solvable in polynomial time. These algorithms exploit an interesting relation of the game and minimum vertex cuts in certain graph classes. Finally, we show that the problem is fixed-parameter tractable parameterized by both the graphs neighborhood diversity and $tau$.
Many real-world networks exhibit correlations between the node degrees. For instance, in social networks nodes tend to connect to nodes of similar degree. Conversely, in biological and technological networks, high-degree nodes tend to be linked with
Motivated by recent computational models for redistricting and detection of gerrymandering, we study the following problem on graph partitions. Given a graph $G$ and an integer $kgeq 1$, a $k$-district map of $G$ is a partition of $V(G)$ into $k$ non
Motivated by applications in gerrymandering detection, we study a reconfiguration problem on connected partitions of a connected graph $G$. A partition of $V(G)$ is emph{connected} if every part induces a connected subgraph. In many applications, it
Multiple interval graphs are variants of interval graphs where instead of a single interval, each vertex is assigned a set of intervals on the real line. We study the complexity of the MAXIMUM CLIQUE problem in several classes of multiple interval gr
Reversible simulation of irreversible algorithms is analyzed in the stylized form of a `reversible pebble game. While such simulations incur little overhead in additional computation time, they use a large amount of additional memory space during the