Author name cluster

E. Dahlhaus

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

TCS Journal 1998 Journal Article

The parallel complexity of approximating the high degree subgraph problem

A.E. Andreev
A. Clementi
P. Crescenzi
E. Dahlhaus
S. De Agostino
J.D.P. Rolim

The high degree subgraph problem is to find a subgraph H of a graph G such that the minimum degree of H is as large as possible. This problem is known to be P-hard so that parallel approximation algorithms are very important for it. Our first goal is to determine how effectively the approximation algorithm based on a well-known extremal graph result parallelizes. In particular, we show that two natural decision problems associated with this algorithm are P-complete: these results suggest that the parallel implementation of the algorithm itself requires more sophisticated techniques. Successively, we study the high degree subgraph problem for random graphs with any edge probability function and we provide different parallel approximation algorithms depending on the type of this function.

Details DOI

I&C Journal 1992 Journal Article

Query languages for hierarchic databases

E. Dahlhaus
J.A. Makowsky

We generalize relational data bases such as to include also hierarchic structures in the form of directories of relations and directories of directories. In this framework we study computable directory transformations which generalize the computable queries introduced by A. Chandra and D. Harel. We introduce a transformation language DL and show its completeness. The language DL can serve as a basis for specification and correctness of directory transformations and also as a basis to study their complexity. The method developed can be seen also in a broader context: It allows the general manipulation of “objects” (as in Smalltalk or SETL) and adds to it a construct for parallelism (as in VAL). We also discuss the relationship of our approach to various other models of hierarchic and object-oriented database models.

Details DOI

TCS Journal 1985 Journal Article

Concerning two-adjacent context-free languages

E. Dahlhaus
H. Gaifman

This paper presents a negative solution of the problem whether 2-adjacent context-free languages and context-free languages coincide. Moreover, we compare this language type with E0L-languages.

Details DOI