TY - GEN
AU - Peckhaus, Volker
ID - 18203
T2 - Zentralblatt für Mathematik und ihre Grenzgebiete [Zbl. 863.03005]
TI - Temple, George, “Fundamental Mathematical Theories”, Philos. Trans. R. Soc. Lond., Ser. A 354, No. 1714 (1996), 1941–1967
ER -
TY - GEN
AU - Peckhaus, Volker
ID - 18208
T2 - Zentralblatt für Mathematik und ihre Grenzgebiete [Zbl. 873.01015]
TI - Benmakhlouf, Ali, Gottlob Frege. Logicien philosophe, Presses Universitaires de France: Paris 1997
ER -
TY - BOOK
ED - Frank, Barbara
ED - Haye, Thomas
ED - Tophinke, Doris
ID - 18551
TI - Gattungen mittelalterlicher Schriftlichkeit
ER -
TY - CONF
AU - Sohler, Christian
AU - Denny, Markus
ID - 18575
T2 - Proceedings of the 9th Canadian Conference on Computational Geometry
TI - Encoding a Triangulation as a Permutation of its Point Set
ER -
TY - JOUR
AB - We present a simple analytic scheme for calculating the binding energy of excitons in semiconductors that takes full account of the existing anisotropy in the effective mass, as a complement to the qualitative treatment in most textbooks. Results obtained for excitons in gallium nitride form the basis for a discussion of the accuracy of this approach.
AU - Schindlmayr, Arno
ID - 18626
IS - 5
JF - European Journal of Physics
SN - 0143-0807
TI - Excitons with anisotropic effective mass
VL - 18
ER -
TY - GEN
AB - In this paper we present a (randomized) algorithm for maintaining the biconnected components of a dynamic planar graph of $n$ vertices under deletions of edges. The biconnected components can be maintained under any sequence of edge deletions in a total of $O(n log n)$ time, with high probability. This gives $O(log n)$ amortized time per edge deletion, which improves previous (deterministic) results due to Giammarresi and Italiano, where $O(n log^2 n)$ amortized time is needed. Our work describes a simplification of the data structures from [GiIt96] and uses dynamic perfect hashing to reduce the running time. As in the paper by Giammarresi and Italiano, we only need $O(n)$ space. Finally we describe some simply additional operations on the decremental data structure. By aid of them this the data structure is applicable for finding efficiently a $Delta$-spanning tree in a biconnected planar graph with a maximum degree $2Delta-2$ do to Czumaj and Strothmann.
AU - Strothmann, Willy-Bernhard
AU - Lukovszki, Tamás
ID - 18955
TI - Decremental Biconnectivity on Planar Graphs
ER -
TY - JOUR
AU - Eke, Norbert Otto
ID - 19410
IS - H. 4
JF - Deutsche Vierteljahrsschrift für Literaturwissenschaft und Geistesgeschichte
TI - Planziel Vernichtung. Zwei Versuche über das Unfaßbare des Völkermords: Franz Werfels Die vierzig Tage des Musa Dagh (1933) und Edgar Hilsenraths Das Märchen vom letzten Gedanken (1989)
VL - 71
ER -
TY - THES
AU - Dittrich, Wolfgang
ID - 19636
SN - 3-931466-26-4
TI - Communication and I/O Efficient Parallel Data Structures
ER -
TY - THES
AU - Bäumker, Armin
ID - 19631
SN - 3-931466-27-2
TI - Communication Efficient Parallel Searching
ER -
TY - CONF
AB - Given a connected graph $G$, let a $dT$-spanning tree of $G$ be a spanning tree of $G$ of maximum degree bounded by $dT$. It is well known that for each $dT ge 2$ the problem of deciding whether a connected graph has a $dT$-spanning tree is NP-complete. In this paper we investigate this problem when additionally connectivity and maximum degree of the graph are given. A complete characterization of this problem for 2- and 3-connected graphs, for planar graphs, and for $dT=2$ is provided. Our first result is that given a biconnected graph of maximum degree $2dT-2$, we can find its $dT$-spanning tree in time $O(m+n^3/2)$. For graphs of higher connectivity we design a polynomial-time algorithm that finds a $dT$-spanning tree in any $k$-connected graph of maximum degree $k(dT-2)+2$. On the other hand, we prove that deciding whether a $k$-connected graph of maximum degree $k(dT-2)+3$ has a $dT$-spanning tree is NP-complete, provided $k le 3$. For arbitrary $k ge 3$ we show that verifying whether a $k$-connected graph of maximum degree $k(dT-1)$ has a $dT$-spanning tree is NP-complete. In particular, we prove that the Hamiltonian path (cycle) problem is NP-complete for $k$-connected $k$-regular graphs, if $k>2$. This extends the well known result for $k=3$ and fully characterizes the case $dT=2$. For planar graphs it is NP-complete to decide whether a $k$-connected planar graph of maximum degree $dG$ has a $dT$-spanning tree for $k=1$ and $dG > dT ge 2$, for $k=2$ and $dG > 2(dT-1) ge 2$, and for $k=3$ and $dG > dT = 2$. On the other hand, we show how to find in polynomial (linear or almost linear) time a $dT$-spanning tree for all other parameters of $k$, $dG$, and $dT$.
AU - Czumaj, Artur
AU - Strothmann, Willy-B.
ID - 19869
SN - 0302-9743
T2 - Proceedings of the Fifth Annual European Symposium on Algorithms (ESA'97)
TI - Bounded degree spanning trees
ER -