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 -
TY - CONF
AU - Hahn, O.
AU - Meschut, Gerson
ID - 20739
T2 - Tagungsband zur Swiss Bonding ´97
TI - Bonding of Aluminium Profile joints
ER -
TY - JOUR
AU - Platzner, Marco
AU - Rinner, Bernhard
AU - Weiss, Reinhold
ID - 10609
JF - e & i Elektrotechnik und Informationstechnik
TI - A Computer Architecture to Support Qualitative Simulation in Industrial Applications
VL - 114
ER -
TY - JOUR
AU - Platzner, Marco
AU - Rinner, Bernhard
AU - Weiss, Reinhold
ID - 10724
IS - 7-8
JF - Simulation Practice and Theory
TI - Parallel qualitative simulation
VL - 5
ER -
TY - GEN
AU - Hertwig, Andre
AU - Hellebrand, Sybille
AU - Wunderlich, Hans-Joachim
ID - 13090
KW - WORKSHOP
TI - Synthesis of Fast On-Line Testable Controllers for Data-Dominated Applications
ER -
TY - CONF
AU - Platzner, Marco
AU - Peters, Liliane
ID - 13603
T2 - Proceedings of the SPIE: Conference on Parallel and Distributed Methods for Image Processing
TI - Fast Signature Segmentation on a Multi-DSP Architecture
VL - 3166
ER -
TY - JOUR
AU - Großner, U.
AU - Schmidt, Wolf Gero
AU - Bechstedt, F.
AU - Santos, P.V.
AU - Koopmans, B.
AU - Esser, N.
ID - 13778
JF - Surface Science
SN - 0039-6028
TI - Chemisorption of arsenic on InP(110)
VL - 377-379
ER -
TY - JOUR
AU - Schmidt, Wolf Gero
AU - Bechstedt, F.
ID - 13780
IS - 19
JF - Physical Review B
SN - 0163-1829
TI - Antimony-stabilized GaAs(001)(2×4) reconstructions
VL - 55
ER -
TY - BOOK
ED - Hagengruber, Ruth
ED - Stein, Otti
ED - Wedig, Sigrid
ID - 15611
SN - 3928961152
TI - Begegnungen mit Philosophinnen : Seminar "Feministische Ethik"
ER -