Source author record

Meike Hatzel

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Logic in Computer Science Discrete Mathematics math.CO

Catalog footprint

Research overview

3works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Simpler and faster algorithms for detours in planar digraphs

In the directed detour problem one is given a digraph $G$ and a pair of vertices $s$ and~ $t$ , and the task is to decide whether there is a directed simple path from $s$ to $t$ in $G$ whose length is larger than $\mathsf{dist}_{G}(s,t)$ . The more general parameterized variant, directed long detour, asks for a simple $s$ -to- $t$ path of length at least $\mathsf{dist}_{G}(s,t)+k$ , for a given parameter $k$ . Surprisingly, it is still unknown whether directed detour is polynomial-time solvable on general digraphs. However, for planar digraphs, Wu and Wang~[Networks, '15] proposed an $\mathcal{O}(n^3)$ -time algorithm for directed detour, while Fomin et al.~[STACS 2022] gave a $2^{\mathcal{O}(k)}\cdot n^{\mathcal{O}(1)}$ -time fpt algorithm for directed long detour. The algorithm of Wu and Wang relies on a nontrivial analysis of how short detours may look like in a plane embedding, while the algorithm of Fomin et al.~is based on a reduction to the $§$ -disjoint paths problem on planar digraphs. This latter problem is solvable in polynomial time using the algebraic machinery of Schrijver~[SIAM~J.~Comp.,~'94], but the degree of the obtained polynomial factor is huge. In this paper we propose two simple algorithms: we show how to solve, in planar digraphs, directed detour in time $\mathcal{O}(n^2)$ and directed long detour in time $2^{\mathcal{O}(k)}\cdot n^4 \log n$ . In both cases, the idea is to reduce to the $2$ -disjoint paths problem in a planar digraph, and to observe that the obtained instances of this problem have a certain topological structure that makes them amenable to a direct greedy strategy.

preprint2015arXiv

Encoding CSP into CCS

We study encodings from CSP into asynchronous CCS with name passing and matching, so in fact, the asynchronous pi-calculus. By doing so, we discuss two different ways to map the multi-way synchronisation mechanism of CSP into the two-way synchronisation mechanism of CCS. Both encodings satisfy the criteria of Gorla except for compositionality, as both use an additional top-level context. Following the work of Parrow and Sjödin, the first encoding uses a centralised coordinator and establishes a variant of weak bisimilarity between source terms and their translations. The second encoding is decentralised, and thus more efficient, but ensures only a form of coupled similarity between source terms and their translations.

preprint2015arXiv

Encoding CSP into CCS (Extended Version)

We study encodings from CSP into asynchronous CCS with name passing and matching, so in fact, the asynchronous pi-calculus. By doing so, we discuss two different ways to map the multi-way synchronisation mechanism of CSP into the two-way synchronisation mechanism of CCS. Both encodings satisfy the criteria of Gorla except for compositionality, as both use an additional top-level context. Following the work of Parrow and Sjödin, the first encoding uses a central coordinator and establishes a variant of weak bisimilarity between source terms and their translations. The second encoding is decentralised, and thus more efficient, but ensures only a form of coupled similarity between source terms and their translations.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.