@inproceedings{19869,
abstract = {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$.},
author = {Czumaj, Artur and Strothmann, Willy-B.},
booktitle = {Proceedings of the Fifth Annual European Symposium on Algorithms (ESA'97)},
isbn = {9783540633976},
issn = {0302-9743},
title = {{Bounded degree spanning trees}},
doi = {10.1007/3-540-63397-9_9},
year = {1997},
}
@inproceedings{20739,
author = {Hahn, O. and Meschut, Gerson},
booktitle = {Tagungsband zur Swiss Bonding ´97},
location = {Rapperswil (CH)},
title = {{Bonding of Aluminium Profile joints}},
year = {1997},
}
@article{10609,
author = {Platzner, Marco and Rinner, Bernhard and Weiss, Reinhold},
journal = {e & i Elektrotechnik und Informationstechnik},
pages = {13--18},
publisher = {Springer},
title = {{A Computer Architecture to Support Qualitative Simulation in Industrial Applications}},
volume = {114},
year = {1997},
}
@article{10724,
author = {Platzner, Marco and Rinner, Bernhard and Weiss, Reinhold},
journal = {Simulation Practice and Theory},
number = {7-8},
pages = {623--638},
publisher = {Elsevier},
title = {{Parallel qualitative simulation}},
doi = {10.1016/s0928-4869(97)00008-6},
volume = {5},
year = {1997},
}
@misc{13090,
author = {Hertwig, Andre and Hellebrand, Sybille and Wunderlich, Hans-Joachim},
keyword = {WORKSHOP},
title = {{Synthesis of Fast On-Line Testable Controllers for Data-Dominated Applications}},
year = {1997},
}
@inproceedings{13603,
author = {Platzner, Marco and Peters, Liliane},
booktitle = {Proceedings of the SPIE: Conference on Parallel and Distributed Methods for Image Processing},
title = {{Fast Signature Segmentation on a Multi-DSP Architecture}},
volume = {3166},
year = {1997},
}
@article{13778,
author = {Großner, U. and Schmidt, Wolf Gero and Bechstedt, F. and Santos, P.V. and Koopmans, B. and Esser, N.},
issn = {0039-6028},
journal = {Surface Science},
pages = {619--622},
title = {{Chemisorption of arsenic on InP(110)}},
doi = {10.1016/s0039-6028(96)01469-0},
volume = {377-379},
year = {1997},
}
@article{13780,
author = {Schmidt, Wolf Gero and Bechstedt, F.},
issn = {0163-1829},
journal = {Physical Review B},
number = {19},
pages = {13051--13057},
title = {{Antimony-stabilized GaAs(001)(2×4) reconstructions}},
doi = {10.1103/physrevb.55.13051},
volume = {55},
year = {1997},
}
@book{15611,
editor = {Hagengruber, Ruth and Stein, Otti and Wedig, Sigrid},
isbn = {3928961152},
publisher = {Quast-Verlag},
title = {{Begegnungen mit Philosophinnen : Seminar "Feministische Ethik" }},
year = {1997},
}
@inproceedings{15034,
author = {Volbracht, Sabine and Domik, Gitta and Shahrbabaki, Khatoun and Fels, Gregor},
booktitle = {Proceedings of the ACM SIGCHI Conference on Human factors in computing systems},
pages = {540--541},
title = {{How effective are 3D display modes?}},
year = {1997},
}