@PHDTHESIS\{IMM2005-03863,
    author       = "T. Thomadsen",
    title        = "Hierarchical Network Design",
    year         = "2005",
    school       = "Informatics and Mathematical Modelling, Technical University of Denmark, {DTU}",
    address      = "Richard Petersens Plads, Building 321, {DK-}2800 Kgs. Lyngby",
    type         = "",
    note         = "Supervised by prof. Jens Clausen, {IMM}",
    url          = "http://www2.compute.dtu.dk/pubdb/pubs/3863-full.html",
    abstract     = "Communication networks are immensely important today, since both companies and individuals use numerous services that rely on them. This thesis considers the design of hierarchical (communication) networks. Hierarchical networks consist of layers of networks and are well-suited for coping with changing and increasing demands. Two-layer networks consist of one backbone network, which interconnects cluster networks. The clusters consist of nodes and links, which connect the nodes. One node in each cluster is a hub node, and the backbone interconnects the hub nodes of each cluster and thus the clusters. The design of hierarchical networks involves clustering of nodes, hub selection, and network design, i.e. selection of links and routing of  ows.

Hierarchical networks have been in use for decades, but integrated design of these networks has only been considered for very special types of networks. The thesis investigates models for hierarchical network design and methods used to design such networks. In addition, ring network design is considered, since ring networks commonly appear in the design of hierarchical networks.

The thesis introduces hierarchical networks, including a classification scheme of different types of hierarchical networks. This is supplemented by a review of ring network design problems and a presentation of a model allowing for modeling most hierarchical networks. We use methods based on linear programming to design the hierarchical networks. Thus, a brief introduction to the various linear programming based methods is included. The thesis is thus suitable as a foundation for study of design of hierarchical networks.

The major contribution of the thesis consists of seven papers which are included
in the appendix. The papers address hierarchical network design and/or ring network design. The papers have all been submitted for journals, and except for two papers, are awaiting review. The papers are mostly concerned with optimal methods and, in a few cases, heuristics for designing hierarchical and ring networks. All papers develop bounds which are used in the optimal methods and for comparison. Finally, computational results are reported.

In Danish:

Kommunikationsnetv{\ae}rk har enorm betydning i dag, da enkeltpersoner og virksomheder anvender utallige tjenester, som afh nger af kommunikationsnetv{\ae}rkene. Denne afhandling omhandler design af hierarkiske (kommunikations-) netv{\ae}rk. Hierarkiske netv{\ae}rk er lagdelte og er velegnede til at h{\aa}ndtere {\ae}ndringer og  gede i krav til b{\aa}ndbredde. Netv{\ae}rk med to niveauer best{\aa}r af et backbone netv rk som forbinder klynger af netv{\ae}rksknuder. Klyngerne best{\aa}r af netv{\ae}rksknuder og forbindelser mellem netv{\ae}rksknuderne internt i klyngen. I hver klynge er en af netv{\ae}rksknuderne udpeget som hoved-netv{\ae}rksknuden, dvs. den har forbindelse til backbone netv{\ae}rket. Backbone netv{\ae}rket forbinder hoved-netv{\ae}rksknuderne og dermed klyngerne. For at designe et hierarkisk netv{\ae}rk, skal der tages stilling til hvilke netv{\ae}rksknuder der er i hvilken klynge, hoved-netv{\ae}rksknuderne skal udv{\ae}lges, netv{\ae}rksknuderne skal forbindes b{\aa}de i klyngerne og i backbone netv{\ae}rket, og tra k skal rutes i netv{\ae}rket.

Hierarkiske netv{\ae}rk har v{\ae}ret anvendt i  artier, men design af disse netv{\ae}rk er kun blevet unders{\o}gt for specielle netv{\ae}rkstyper. Denne afhandling unders{\o}ger modeller til design af hierarkiske netv{\ae}rk og metoder der kan anvendes til at designe hierarkiske netv{\ae}rk. Derudover unders{\o}ges ring netv{\ae}rk, da ring netv{\ae}rk ofte forekommer i design af hierarkiske netv{\ae}rk.

Afhandlingen introducerer hierarkiske netv{\ae}rk, inklusive et klassifikationsskema af de forskellige typer af hierarkiske netv{\ae}rk. Dette bliver suppleret med en gennemgang af ring netv{\ae}rk problemer og en pr{\ae}sentation af en generel model, der tillader modellering af de  este hierarkiske netv{\ae}rk. Metoder baseret p{\aa} line{\ae}r programmering introduceres, idet de anvendes til design af hierarkiske netv{\ae}rk. Afhandlingen kan s{\aa}ledes danne grundlag for et studie af design af hierarkiske netv{\ae}rk.

Afhandlings vigtigste bidrag best ar af syv artikler, der er inkluderet i appendiks. Artiklerne handler om design af hierarkisk netv{\ae}rk og ring netv{\ae}rk. Artiklerne er alle indsendt til videnskablige journaler og afventer bed{\o}mmelse, bortset fra to artikler, der allerede er blevet accepteret. Artiklerne beskriver oftest optimale metoder og i enkelte tilf{\ae}lde heuristikker til at design hierarkiske netv{\ae}rk samt ring netv{\ae}rk. I alle tilf{\ae}lde er der udviklet gr{\ae}nser, der kan anvendes enten til sammenligning eller indlejret i de optimale metoder. Endelig pr{\ae}senteres resultater for testk{\o}rsler af metoderne."
}