Wooden Geometric Puzzles: Design and Hardness Proofs Helmut Alt (2008)
We discuss some new geometric puzzles and the complexity of their extension to arbitrary sizes. For gate puzzles and two-layer puzzles we prove NP-completeness of solving them. Not only the solution...
Complexity Results for Enhanced Qualitative Probabilistic Networks (2008)
While quantitative probabilistic networks (QPNs) allow the expert to state influences between nodes in the network as influence signs, rather than conditional probabilities, inference in these...
Core Matter The ABCDE Format Enabling Semantic Conference Proceedings (2008)
– We believe that the best way to present a narrative to a computer is to let the author explicitly create a rich semantic structure for the article during writing. – We propose an open-standard,...
Wooden Geometric Puzzles: Design and Hardness Proofs (2008)
Hans L. Bodlaender, Marc Van Kreveld, Günter Rote, Gerard Tel, Helmut Alt, Hans L. Bodlaender, ...
We discuss some new geometric puzzles and the complexity of their extension to arbitrary sizes. For gate puzzles and two-layer puzzles we prove NP-completeness of solving them. Not only the solution...
Helmut Alt, Hans L. Bodlaender, Marc Kreveld, Gerard Tel, Gerard Tel
Abstract We discuss some new geometric puzzles and the complexity of their extension to arbitrary sizes. For gate puzzles and two-layer puzzles we prove NP-completeness of solving them. Not only the...
Complexity Results for Local Monotonicity in Probabilistic Networks (2008)
Johan Kwisthout, Hans L. Bodlaender, Gerard Tel, Johan Kwisthout, Hans L. Bodlaender, Gerard Tel
Often, monotonicity is a desirable property of probabilistic networks. For example, when medical knowledge in a particular domain dictates that more severe symptoms increase the likeliness of a more...
Local monotonicity in probabilistic networks (2007)
Johan Kwisthout, Hans Bodlaender, Gerard Tel
Abstract. It is often desirable that a probabilistic network is monotone, e.g., more severe symptoms increase the likeliness of a more serious disease. Unfortunately, determining whether a network is...
Local monotonicity in probabilistic networks (2007)
Johan Kwisthout, Hans Bodlaender, Gerard Tel
In many probabilistic networks [3] that are used for classification in real problem domains, the variables of the network can be distinguished into observable input variables, non-observable...
Complexity Results for Enhanced Qualitative Probabilistic Networks (2006)
Johan Kwisthout, Gerard Tel, Johan Kwisthout, Gerard Tel
While quantitative probabilistic networks (QPNs) allow experts to state influences between nodes in the network as influence signs, rather than conditional probabilities, inference in these networks...
Rectilinear graphs and angular resolution (2003)
Hans L. Bodlaender, Gerard Tel
In this note we show that a planar graph with angular resolution at least #/2 can be drawn with all angles an integer multiple of #/2, that is, in a rectilinear manner. Moreover, we show that for d...
Rectilinear graphs and angular resolution (2003)
Hans L. Bodlaender, Gerard Tel
In this note we show that a planar graph with angular resolution at least π/2 can be drawn with all angles an integer multiple of π/2, that is, in a rectilinear manner. Moreover, we show that for d...
Partially supported by the Future and Emerging Technologies programme of the EU (2003)
Hans L. Bodlaender, Gerard Tel
We connect two aspects of graph drawing, namely angular resolution, and the possibility to draw with all angles an integer multiple of 2π/d. A planar graph with angular resolution at least π/2...
Distributed Control for AI (1998)
This paper discusses a number of elementary problems in distributed computing and a couple of well-known algorithmic "building blocks", which are used as procedures in distributed...
Distributed Graph Exploration (1997)
This article describes algorithms to compute spanning trees in an undirected network, that is, partition the set of edges into tree edges (these will be directed from parent to child) and non-tree...
Synchronous, Asynchronous, and Causally Ordered Communication (1995)
Bernadette Charron-Bost, Friedemann Mattern, Gerard Tel
This article studies characteristic properties of synchronous and asynchronous message communications in distributed systems. Based on the causality relation between events in computations with...
Synchronizing ABD networks (1994)
Gerard Tel, Gerard Tel, Shmuel Zaks, Shmuel Zaks, Ephraim Korach, Ephraim Korach, ...
z We present in this paper a simple and efficient synchronizer algorithm for Asynchronous Bounded Delay Networks. In these networks each processor has a local clock, and the message delay is bounded...
This paper analyses how the symmetry of a processor network influences the existence of a solution for the network orientation problem. The orientation of cliques, hypercubes and tori is the problem...
An Assertional Proof of Rana's Algorithm (1994)
We give an assertional correctness proof for a version of Rana's termination detection algorithm. Safety is shown by means of reasoning with invariants, and liveness by means of a norm function,...
Gerard Tel, Friedemann Mattern
It is shown that the termination detection problem for distributed computations can be modeled as an instance of the garbage collection problem. Consequently, algorithms for the termination detection...
Linear election for oriented hypercube (1993)
In this article we propose an election algorithm for the oriented hypercube, where each edge is assumed to be labeled with its dimension in the hypercube. The algorithm exchanges O(N) messages and...
Gerard Tel, Friedemann Mattern
It is shown that the termination detection problem for distributed computations can be modeled as an instance of the garbage collection problem. Consequently, algorithms for the termination detection...
Gerard Tel, Friedemann Mattern
It is shown that the termination detection problem for distributed computations can be modeled as an instance of the garbage collection problem. Consequently, algorithms for the termination detection...
Gerard Tel, Friedemann Mattern
It is shown that the termination detection problem for distributed computations can be modeled as an instance of the garbage collection problem. Consequently, algorithms for the termination detection...
Global Virtual Time Approximation with Distributed Termination Detection Algorithms (1991)
Friedemann Mattern, Horst Mehl, Anneke A. Schoone, Gerard Tel
It is shown that distributed termination detection algorithms can be transformed into efficient algorithms to approximate the so-called Global Virtual Time (GVT) of a distributed monotonic...
Global Virtual Time Approximation with Distributed Termination Detection Algorithms (1991)
Friedemann Mattern, Horst Mehl, Anneke A. Schoone, Gerard Tel
It is shown that distributed termination detection algorithms can be transformed into efficient algorithms to approximate the so-called Global Virtual Time (GVT) of a distributed monotonic...
Global Virtual Time Approximation with Distributed Termination Detection Algorithms (1991)
Friedemann Mattern, Horst Mehl, Anneke A. Schoone, Gerard Tel
It is shown that distributed termination detection algorithms can be transformed into efficient algorithms to approximate the so-called Global Virtual Time (GVT) of a distributed monotonic...
We define the notion of total algorithms for networks of processes. A total algorithm enforces that a "decision " is taken by a subset of the processes, and that participation of...
Assertional Verification of a Timer-based Protocol (1987)
by an external observer). The task of a transport protocol is to let A and B exchange information in a reliable way. That is, no information may be lost, duplicated or delivered out of order....
Distributed Infimum Approximation (1986)
Abstract: A "distributed infimum " is the infimum of a set of values that are distri-buted over the sites and channels in a distributed system. The values in the set are as-sumed to...