Gargano, Luisa; Hell, Pavol; Stacho, Ladislav; Vaccaro, Ugo Spanning trees with bounded number of branch vertices. (English) Zbl 1056.68587 Widmayer, Peter (ed.) et al., Automata, languages and programming. 29th international colloquium, ICALP 2002, Málaga, Spain, July 8–13, 2002. Proceedings. Berlin: Springer (ISBN 3-540-43864-5). Lect. Notes Comput. Sci. 2380, 355-365 (2002). Summary: We introduce the following combinatorial optimization problem: Given a connected graph \(G\), find a spanning tree \(T\) of \(G\) with the smallest number of branch vertices (vertices of degree 3 or more in \(T\)). The problem is motivated by new technologies in the realm of optical networks. We investigate algorithmic and combinatorial aspects of the problem.For the entire collection see [Zbl 0993.00041]. Cited in 1 ReviewCited in 28 Documents MSC: 68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) 68M10 Network design and communication in computer systems 90C27 Combinatorial optimization 90C35 Programming involving graphs or networks 68R10 Graph theory (including graph drawing) in computer science PDFBibTeX XMLCite \textit{L. Gargano} et al., Lect. Notes Comput. Sci. 2380, 355--365 (2002; Zbl 1056.68587) Full Text: Link