Feszítőfa optimalizálási problémák a Hamilton utak általánosítására

Spanning tree optimization problems generalizing the notion of Hamiltonian path

Salamon, Gábor

Bitay, Enikő

Erdélyi Múzeum-Egyesület

2011-06-08T20:48:35Z

2011-06-08T20:48:35Z

2008

Abstract The design process of telecommunication networks often uses graph theory as an efficient modeling paradigm. The nodes and possible links of the network are represented by a graph G. When a connected network is to be designed, the aim is to find a spanning tree T of input graph G. Many of these problems have an objective function based on the node-degrees of T. This model is extremely useful while designing networks where the cost of devices to install depends highly on the needed routing functionality (ending, forwarding, or routing a connection). In this paper we consider three closely related problems of this kind: Minimum Leaf Spanning Tree problem, Maximum Internal Spanning Tree problem, and Minimum Branching Spanning Tree problem. All of these problems are generalizations of the Hamiltonian path problem as a Hamiltonian path of the input graph G (if exists) provides an optimal solution for all of them. As a result all three problems are NP-hard and so it is very unlikely that exact polynomial time algorithms can be developed for them. Research activity on this topic focuses on creating approximation algorithms which provide „good enough” solutions in polynomial time. In this paper we survey the known approximability results on the above problems. The approximation algorithms can be used in network design either to directly solve problems or to build up efficient solution heuristics. Összefoglalás A távközlési hálózatok tervezésekor az egyik leggyakrabban használt modellezési paradigma a gráfelmélet. A megtervezendő hálózat csomópontjait és lehetséges összeköttetéseit egy G gráf írja le. Amennyiben a célunk egy összefüggő hálózat kialakítása, tulajdonképpen ebben a G input gráfban kell egy T feszítőfát találnunk. Sok konkrét hálózattervezési feladat esetében a T megoldás jóságát leíró célfüggvény a T feszítőfa fokszámaitól függ. Ez a modell igen hasznos például abban az esetben, amikor a hálózati csomópontokba elhelyezendő eszközök költségét a tőlük megkövetelt funkcionalitás (kapcsolat végződtetés, adat továbbítás, útvonalválasztás) határozza meg. A jelen dolgozatban három olyan problémát ismertetünk, melyek a fokszám-alapú feszítőfa optimalizálás témakörébe tartoznak: a MINIMÁLIS LEVÉLSZÁMÚ FESZÍTŐFA, a MAXIMÁLIS BELSŐPONT-SZÁMÚ FESZÍTŐFA és a MINIMÁLIS ELÁGAZÁSSZÁMÚ FESZÍTŐFA problémákat. Ezen problémák mindegyike a Hamilton-út keresés általánosítása (tehát NP-nehéz), ezért nagyon valószínűtlen, hogy a közeljövőben egyszerre egzakt és hatékony algoritmust találjunk megoldásukra. A témában folyó kutatások egyik fő iránya épp ezért gyors és „elég pontos” közelítő algoritmusok megalkotása. A jelen dolgozatban összefoglaljuk a fenti három problémára jelenleg ismert közelítéseket. A hivatkozott algoritmusok közvetlen hasznukon túl ahhoz is hozzájárulnak, hogy a hálózattervezés problémáinak megoldására a jövőben hatékony heurisztikákat találjunk.

203-206

magyar

angol

Article

Adobe PDF

application/pdf

978-973-8231-75-7

http://hdl.handle.net/10598/14830

Erdélyi Múzeum-Egyesület

Fiatal Műszaki Tudományos Ülésszaka 12

© Erdélyi Múzeum-Egyesület