Koster A., Munoz X. Graphs and Algorithms in Communication Networks
Подождите немного. Документ загружается.
1 Graphs and Algorithms in Communication Networks on Seven League Boots 51
(a) operated frequency plan (b) optimized frequency plan
Fig. 1.14 Interference reduction of 96% by heuristics.
In the most simple version, the main objective is to maximize the area covered
by the installed antennae, given a certain budget; or alternatively, to minimize the
installation cost subject to the requirement of covering a certain percentage of the
area, e.g., 99%.
To measure the coverage of a wireless network within a region (e.g., building,
city center, county, country), a grid of pixels I representing small areas is laid out.
A set of possible locations for antennae A is introduced, with cost parameter c
a
for
installing an (omnidirectional) antenna.
For each antenna location a ∈ A, we introduce a binary variable x
a
∈{0,1} to
denote whether or not an antenna is installed at this location. To model the con-
straints, we introduce sets A
i
⊆ A defining which antennae locations would be able
to cover pixel i ∈I (assuming a particular configuration of antenna a ∈A). Now, the
minimum cost 100% coverage problem reads
min
∑
a∈A
c
a
x
a
(1.28a)
s.t.
∑
a∈A
i
x
a
≥ 1 ∀i ∈ I (1.28b)
x
a
∈{0,1} (1.28c)
This model precisely describes a minimum cost set covering problem for base set I
with subsets I
a
= {i ∈I |a ∈A
i
}. Hence, the problem is NP-hard.
Coverage rates below 100% can also be modeled with an extra set of binary
variables y
i
∈{0, 1} denoting whether or not a pixel is covered. If p denotes the
percentage of pixels to be covered, the new model reads
52 A. M. C. A. Koster, X. Mu
˜
noz
min
∑
a∈A
c
a
x
a
(1.29a)
s.t.
∑
a∈A
i
x
a
−y
i
≥ 0 ∀i ∈ I (1.29b)
∑
i∈I
y
i
≥ p
|
I
|
(1.29c)
x
a
,y
i
∈{0,1} (1.29d)
Constraints (1.29b) now require an antenna installed close to pixel i in order to set
y
i
to one. Constraints (1.29c) ensure that p% of the pixels are covered.
An alternative is to maximize the network coverage, given a certain budget B for
network installation cost:
max
∑
i∈I
y
i
(1.30a)
s.t.
∑
a∈A
i
x
a
−y
i
≥ 0 ∀i ∈ I (1.30b)
∑
a∈A
c
a
x
a
≤ B (1.30c)
x
a
,y
i
∈{0,1} (1.30d)
A final generalization to be discussed here is the inclusion of a bandwidth capacity
constraint. For this, a traffic value d
i
is estimated for each pixel i ∈ I and an antenna
capacity D is given. Since we now need to know which pixel is covered by which
antenna, we have to introduce a new set of binary variables z
ia
∈{0,1} for all i ∈ I
and a ∈ A
i
to denote this assignment. Without further restrictions, the model 100%
coverage problem can now be described as
min
∑
a∈A
c
a
x
a
(1.31a)
s.t.
∑
a∈A
i
z
ia
= 1 i ∈ I (1.31b)
∑
i∈I
a
d
i
z
ia
−Dx
a
≤ 0 a ∈ A (1.31c)
x
a
,z
ia
∈{0,1} (1.31d)
Constraints (1.31c) limit the number of test points assigned to an antennae on the
basis of demand and capacity (and only if the antenna location is chosen). This
problem is a special case of the (capacitated) facility location problem (the differ-
ence being that no assignment costs exist); see [62].
All above presented models are simplified in the sense that important issues in
wireless networks are missing. A cell in a wireless network is defined as all pixels
assigned to a single antenna. Cells are usually expected to have a certain degree of
connectedness, but this aspect is completely ignored in the above models. In fact,
the connectedness is (partly) implied by the signal strengths received at the pixel.
1 Graphs and Algorithms in Communication Networks on Seven League Boots 53
The strongest signal determines the allocation of the pixel to an antenna. This and
other issues are studied in depth in Chapter 11. An approach combining frequency
assignment and network coverage is also presented.
1.6 Emerging Applications in Communication Networks
The subsequent chapters of this book are devoted to the application of graph-
theoretical concepts and algorithms to emerging communication networking ap-
plications. The chapters consider problems that have been studied in the context
of the European COST action 293 – Graphs and Algorithms in Communication
Networks [33]. According to the COST 293 working groups, Part I discusses top-
ics in the area of Broadband and Optical Networks, including multilayer networks,
whereas Part II describes studies in Wireless and Ad Hoc Networks. Here we pro-
vide a brief overview.
1.6.1 Broadband and Optical Networks
Chapter 2 presents a survey on theoretical and practical aspects of traffic groom-
ing in optical networks. Traffic grooming was one of the key research topics within
COST 293, and accordingly many participants have contributed to this chapter. The
chapter was coordinated by David Coudert. In high-speed optical networks, every
optical channel provides a huge amount of bandwidth. A single (aggregated) re-
quest usually does not require the whole bandwidth an optical channel provides.
This implies an opportunity to save devices like light termination equipment (trans-
mitters and receivers) and Add/Drop Multiplexers (ADMs) in order to reduce the
investment and operation cost of the network. Chapter 2 surveys the main theoret-
ical results for different grooming factors on various topologies, introduces an ILP
formulation for the optimization problem on general topologies, and presents some
experimental results.
Next, in Chapter 3 the closely related problem of multilayer network design
is discussed. The chapter, coordinated by Sebastian Orlowski, introduces a two-
layer network design problem which has been studied in collaboration with Nokia
Siemens Networks. A mixed-integer programming formulation is presented that
takes many practical side constraints into account, including node hardware, several
bit rates, and survivability against single physical node or link failures. The model is
solved by a branch-and-cut algorithm using problem-specific preprocessing, MIP-
based heuristics, and cutting planes. The authors show that for realistic instances
computation times can be significantly reduced compared to the black-box solution.
Multi-protocol Label Switching (MPLS) is one of the routing protocols in packet-
oriented communication networks that uses labels attached to the packets to encode
the path the packet should follow through the network. With the increasing num-
54 A. M. C. A. Koster, X. Mu
˜
noz
ber of network nodes to route packets to, it is important to keep the length of the
labels small without losing their flexibility. Chapter 4 addresses this issue from an
optimization point of view. Fernando Solano was the leading author of this chapter.
Chapter 5, coordinated by Jos
´
e L. Marzo and Thomas Stidsen, provides a show-
case on the issue of survivability in networks. Instead of reserving dedicated paths
to assure connections are not lost in the case of a link or node failure, one might
consider the usage of a different set of protection paths for every failure situation.
This chapter formalizes this concept, provides exact and heuristic algorithms for the
online routing problem involved, and finally presents two case studies on the re-
source provisioning and connection availability for both dedicated and shared path
protection in heterogeneous network topologies.
Besides connection-oriented and packet-oriented network technologies, optical
burst switching (OBS) has been proposed as an intermediate solution for all-optical
networks. In Chapter 6 Mirosław Klinkowski and his coauthors discuss routing op-
timization in such networks where buffering is in general not possible and hence the
network is sensitive to congestion and traffic losses. Nonlinear optimization models
for three network loss models are studied and solutions are presented that reduce the
burst loss probability.
Next, the issue of dynamic bandwidth allocation is discussed in Chapter 7, led
by Xavier Hesselbach. To maintain and ensure end-to-end in-sequence routing of
packets, load balancing and bandwidth/flow allocation in MPLS-based architectures
have to be established. Traffic characteristics such as Quality of Service (QoS) and
burstiness are considered.
Chapter 8 discusses optimization problems in the context of the open shortest
path (OSPF) routing protocol for Internet traffic. The main advantage of the short-
est path routing policy is its simplicity, allowing for little administrative overhead.
From the network engineering perspective, however, shortest path routing can pose
problems in achieving satisfactory traffic handling efficiency. The chapter discusses
one of the main tasks when planning such a network: the setting of the adminis-
trative weights of the links such that a globally efficient traffic routing is achieved.
This very difficult optimization problem is considered, models are proposed, and
exact and heuristic solution methods are discussed. The chapter was coordinated by
Andreas Bley and Michał Pi
´
oro.
So far, it has been assumed in all chapters that a central authority is able to
make decisions, or coordinate such decisions that determine the performance of the
network. In Chapter 9 the scenario where such a central authority does not exist are
considered. Network users act in an uncoordinated and selfish manner, affecting the
overall system performance. Issues such as the definition of reasonable and practical
models for studying this kind of behavior or the quantification of the efficiency loss
due to the lack of users’ cooperation are discussed, and results are presented. The
chapter was coordinated by Ioannis Caragiannis.
Finally, Chapter 10 (by Ignasi Sau and Janez
ˇ
Zerovnik) studies the routing of
packets in a timely fashion. The goal is to minimize the number of rounds a routing
protocol needs to send a set of requests using a system of paths in the network. More
information on the network topology (e.g., hexagonal grids) or the set of requests
1 Graphs and Algorithms in Communication Networks on Seven League Boots 55
(e.g., so-called permutation routing or r-central routing) allows for more accurate
results. The chapter surveys the results in the general setting and in particular cases.
1.6.2 Wireless and Ad Hoc Networks
The part on wireless and ad hoc networks starts with a study on Wireless Local Area
Network (WLAN) planning. Chapter 11, coordinated by Di Yuan, considers the op-
timization of such networks, taking into account performance measures like deploy-
ment cost, coverage, capacity, interference, data throughput, and radio resource uti-
lization. Both individual models and an integrated model for placing access points
and channel assignment are presented. Computational results are reported on the
basis of real-life data.
Broadcasting is a basic network communication task, where a message initially
held by a source node has to be disseminated to all other nodes in the network.
Broadcasting in radio networks is studied in Chapter 12. David Peleg and Tomasz
Radzik review the literature on time-efficient algorithms under a variety of models
and assumptions. They also illustrate the basic techniques to prove the obtained
results.
Chapter 13 studies similar problems from the energy consumption perspective. In
wireless networks energy is a scarce resource since many network nodes do not have
a fixed infrastructure (e.g., notebooks, PDAs, etc.). In this chapter, two problems
are studied. The aim of minimum energy broadcast routing is to route a message
from a given source to all other nodes with minimum overall energy usage. In the
Multi-interface Networks, the energy consumption is minimized by the choice of
activated interfaces on devices with multiple interfaces (e.g., Bluetooth, WiFi, etc.).
The leading author of the chapter was Alfredo Navarra.
In contrast to broadcasting, in data gathering information provided or collected
by the network nodes has to be gathered in a specific node. Due to interference,
simultaneous data communication is limited and has to be carried out in a number
of rounds. Hence, minimization of the number of rounds or similar objectives have
to be accounted for. In Chapter 14, Ralf Klasing and his coauthors consider different
interference models and discuss recent complexity results as well as approximation
algorithms.
Chapter 15, by J
´
er
ˆ
ome Galtier, focuses on another aspect of WLANs: protocols
for Medium Access Control (MAC). The transmission of a packet might fail due
to the collision with simultaneously sent packets (from other sources). To achieve a
good network performance, protocols are needed to handle the retransmission of the
packet. In this chapter, mathematical evidence is presented that the selective tourna-
ments protocol is asymptotically tight. Moreover, it is shown that in the context of
WiFi and WiMAX networks a collision reduction of 14% to 21% can be achieved
compared to the best known methods.
Finally, Chapter 16, coordinated by Lenka Carr-Motyckova and Walter Unger),
discusses topology control and routing in ad hoc networks. Mobile entities with
56 A. M. C. A. Koster, X. Mu
˜
noz
the ability to communicate via radio signals may form an ad hoc network. Special
problems arising for these ad hoc networks are considered briefly: range control, the
reduction of interferences, regulation of power consumption, and localization.
Acknowledgements This chapter was supported by EU COST action 293 – Graphs and Algo-
rithms in Communication Networks. The first author was supported by the Centre for Discrete
Mathematics and its Applications (DIMAP), University of Warwick, EPSRC award EP/D063191/1.
References
1. Aardal, K. I., Hoesel, C. P. M. v.: Polyhedral techniques in combinatorial optimization I:
theory. Statistica Neerlandica 50(1), 3–26 (1996)
2. Aardal, K. I., Hoesel, C. P. M. v.: Polyhedral techniques in combinatorial optimization II:
applications and computations. Statistica Neerlandica 53(2), 131–177 (1999)
3. Aardal, K. I., Hoesel, C. P. M. v., Koster, A. M. C. A., Mannino, C., Sassano, A.: Models and
solution techniques for the frequency assignment problem. Annals of Operations Research
153, 79–129 (2007). URL http://dx.doi.org/10.1007/s10479-007-0178-0
4. Aarts, E. H. L., Lenstra, J. K. (eds.): Local Search in Combinatorial Optimization. Wiley,
Chichester (1997)
5. Achterberg, T.: SCIP: solving constraint integer programs. Mathematical Programming Com-
putation 1(1), 1–41 (2009). URL http://scip.zib.de/
6. Agrawal, A., Klein, P., Ravi, R.: When Trees Collide: An Approximation Algorithm for the
Generalized Steiner Problem on Networks. SIAM Journal on Computing 24, 440–456 (1995)
7. Ahuja, R. K., Magnanti, T. L., Orlin, J. B.: Network Flows: Theory, Algorithms, and Applica-
tions. Prentice Hall, New Jersey (1993)
8. Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.:
Complexity and approximation: combinatorial optimization problems and their approximabil-
ity properties. Springer-Verlag (1999)
9. Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications, 2 edn. Springer-
Verlag (2008). http://www.cs.rhul.ac.uk/books/dbook/
10. Bansal, N., Khandekar, R., Nagarajan, V.: Additive guarantees for degree bounded directed
network design. In: Proceedings of the 40th annual ACM symposium on Theory of computing,
STOC 2008, pp. 769–778 (2008)
11. Barnhart, C., Hane, C. A., Vance, P. H.: Using branch-and-price-and-cut to origin-destination
integer multi-commodity flow problems. Operations Research 48, 318–326 (2000)
12. Bazaraa, M. S., Shetty, C. M.: Nonlinear programming: Theory and algorithms. John Wiley
& Sons (1979)
13. Belady, L. A.: A study of replacement algorithms for a virtual-storage computer. IBM Systems
Journal 5(2), 78–101 (1966)
14. Bellare, M., Goldreich, O., Sudan, M.: Free bits, pcps and non-approximability – towards tight
results. SIAM Journal on Computing 27, 804–915 (1998)
15. Bermond, J. C., Delorme, C., Quisquater, J. J.: Strategies for interconnection networks: some
methods from graph theory. Graphs and Combinatorics 5, 107–123 (1989)
16. Bertsekas, D. P.: Nonlinear Programming, 2nd edn. Athena Scientific (1999)
17. Bhandari, R.: Survivable Networks: Algorithms for Diverse Routing. Kluwer Academic Pub-
lishers (1999)
18. Bienstock, D., Bley, A.: Capacitated network design with mulicast commodities. In: Proceed-
ings of 8th International Conference on Telecommunication Systems. Nashville, TN (2000).
URL http://www.zib.de/Publications/abstracts/ZR-00-14/
19. Bienstock, D., Chopra, S., G
¨
unl
¨
uk, O., Tsai, C. Y.: Minimum cost capacity installation for
multicommodity network flows. Mathematical Programming 81, 177–199 (1998)
1 Graphs and Algorithms in Communication Networks on Seven League Boots 57
20. Bixby, R.: Solving real-world linear programs: A decade and more of progress. Operations
Research 50(1), 3–15 (2002)
21. Bixby, R. E., Fenelon, M., Gu, Z., Rothberg, E., Wunderling, R.: Mixed-Integer Programming:
A Progress Report. In: M. Gr
¨
otschel (ed.) The Sharpest Cut: The Impact of Manfred Padberg
and His Work, MPS-SIAM Series on Optimization, vol. 4, pp. 309–326. SIAM (2004)
22. Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications. North-Holland (1976).
http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html
23. Bornd
¨
orfer, R., Eisenbl
¨
atter, A., Gr
¨
otschel, M., Martin, A.: Frequency assignment in cellular
phone networks. Annals of Operations Research 76, 73–94 (1998)
24. Br
´
elaz, D.: New methods to color the vertices of a graph. Communications of the ACM 22,
251–256 (1979)
25. Chartrand, G., Lesniak, L.: Graphs & Digraphs. Wadsworth & Brooks (1986)
26. Chopra, S., Gilboa, I., Sastry, S.: Source sink flows with capacity installation in batches.
DAMATH: Discrete Applied Mathematics and Combinatorial Operations Research and Com-
puter Science 85 (1998)
27. Chopra, S., Rao, M. R.: The Steiner tree problem I: Formulations, compositions and extension
of facets. Mathematical Programming 64, 209–229 (1994)
28. Chung, F. R. K., Coffman, E. G., Reiman, M. I., Simon, B.: On the capacity and forwarding
index of communication networks. IEEE Trans. on Information Theory 33, 244–232 (1987)
29. Chv
´
atal, V.: Linear Programming. W. H. Freeman and Company, New York (1983)
30. Clos, C.: A study of non-blocking switching networks. Bell System Technical Journal (1953)
31. Cook, W.: Fifty-plus years of combinatorial integer programming (2009). URL
http://www2.isye.gatech.edu/
˜
wcook/ip50/ip50.pdf
32. Cook, W. J., Cunningham, W. H., Pulleybank, W. R., Schrijver, A.: Combinatorial Optimiza-
tion. Series in Discrete Mathematics and Optimization. Wiley-Interscience (1998)
33. Cost action 293 – graphs and algorithms in communication networks.
http://www.cost293.org/
34. Coudert, D., Ferreira, A., Mu
˜
noz, X.: A multihop-multi-OPS optical interconnection network.
IEEE/OSA Journal of Lightwave Technology 18(12), 2076–2085 (2000)
35. Coudert, D., Mu
˜
noz, X.: Graph theory and traffic grooming in WDM rings. In: Recent Re-
search Developments in Optics, 3, chap. 37, pp. 759–778. Research Signpost. Kerala, India
(2003)
36. Dantzig, G. B.: Linear Programming and Extensions. Princeton University Press (1998). Orig-
inally published in 1963
37. Dantzig, G. B., Fulkerson, D. R.: On the max-flow min-cut theorem of networks. In: H. W.
Kuhn, A. W. Tucker (eds.) Linear Inequalities and Related Systems, Annals of Mathematics
Series, vol. 38, pp. 215–221. Princeton University Press, Princeton, New Jersey (1956)
38. Diestel, R.: Graph Theory, Graduate Texts in Mathemat-
ics, vol. 173, 3 edn. Springer-Verlag, Heidelberg (2005).
http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/
39. Dijkstra, E. W.: A note on two problems in connexion with graphs. Numerische Mathematik
1, 269–271 (1959)
40. Dolev, D., Halpern, J., Simons, B., Strong, H.: A new look at fault tolerant network routing.
Information and Computation 72, 180–196 (1987)
41. Eisenbl
¨
atter, A.: Frequency assignment in GSM networks: Models, heuristics, and lower
bounds. Ph.D. thesis, Technische Universit
¨
at Berlin, Berlin, Germany (2001)
42. Eisenbl
¨
atter, A.: The semidefinite relaxation of the k-partition polytope is strong. In: W. J.
Cook, A. S. Schulz (eds.) Proceedings of the 9th Conference on Integer Programming and
Combinatorial Optimization (IPCO’02), Lecture Notes in Computer Science, vol. 2337, pp.
273–290. Springer-Verlag, Berlin Heidelberg (2002)
43. Eisenbl
¨
atter, A., Gr
¨
otschel, M., Koster, A. M. C. A.: Frequency planning and ramifications of
coloring. Discussiones Mathematicae Graph Theory
22(1), 51–88 (2002)
44. Eisenbl
¨
atter, A., Koster, A. M. C. A.: FAP web – A website devoted to frequency assignment.
URL: http://fap.zib.de (2000–2008)
58 A. M. C. A. Koster, X. Mu
˜
noz
45. F
`
abrega, J., Fiol, M. A.: Maximally connected digraphs. Journal of Graph Theory 13, 657–668
(1989)
46. Ferreira, A., P
´
erennes, S., Richa, A. W., Rivano, H., Moses, N. S.: Models, Complexity and
Algorithms for the Design of Multifiber WDM Networks. Telecommunication Systems 24,
123–138 (2003)
47. Fiat, A., Karp, R. M., Luby, M., McGeoch, L. A., Sleator, D. D., Young, N. E.: Competitive
paging algorithms. Journal of Algorithms 12(4), 685–699 (1991)
48. Fortz, B., Labb
´
e, M.: Design of survivable networks. In: M. G. C. Resende, P. M. Pardalos
(eds.) Handbook of Optimization in Telecommunications, chap. 15, pp. 367–389. Springer
(2006)
49. Garey, M. R., Johnson, D. S.: The rectilinear Steiner tree problem is NP-complete. SIAM
Journal on Applied Mathematics 32, 826–834 (1977)
50. Garey, M. R., Johnson, D. S.: Computers and intractability: a guide to the theory of
NP-
completeness. Freeman and Company, N. Y. (1979)
51. Goemans, M. X.: Minimum bounded degree spanning trees. In: Proceedings of the 47th
Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006, pp. 273–282
(2006)
52. Gr
¨
otschel, M., Krumke, S. O., Rambau, J. (eds.): Online Optimization of Large Scale Systems.
Springer (2001)
53. Gr
¨
otschel, M., Lov
´
asz, L., Schrijver, A.: The ellipsoid method and its consequences in com-
binatorial optimization. Combinatorica 1, 169–197 (1981)
54. Gr
¨
otschel, M., Lov
´
asz, L., Schrijver, A.: Corrigendum to our paper “the ellipsoid method and
its consequences in combinatorial optimization”. Combinatorica 4, 291–295 (1984)
55. Gr
¨
otschel, M., Lov
´
asz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimiza-
tion. No. 2 in Algorithms and Combinatorics. Springer-Verlag (1988)
56. Gr
¨
otschel, M., Monma, C. L., Stoer, M.: Facets for polyhedra arising in the design of com-
munication networks with low-connectivity constraints. SIAM Journal on Optimization 2(3),
474–504 (1992)
57. Gr
¨
otschel, M., Monma, C. L., Stoer, M.: Design of Survivable Networks. In: M. O. Ball, T. L.
Magnanti, C. L. Monma, G. L. Nemhauser (eds.) Network Models, Handbooks in Operations
Research and Management Science, vol. 7, pp. 617–672. North-Holland (1995)
58. Gr
¨
otschel, M., Monma, C. L., Stoer, M.: Polyhedral and Computational Investigations for
Designing Communication Networks with High Survivability Requirements. Operations Re-
search 43(6), 1012–1024 (1995)
59. Grover, W. D.: Mesh-based Survivable Networks: Options and Strategies for Optical, MPLS,
SONET and ATM Networking. Prentice Hall (2003)
60. Henningsson, M., Holmberg, K., Yuan, D.: Ring network design. In: M. G. C. Resende, P. M.
Pardalos (eds.) Handbook of Optimization in Telecommunications, chap. 12, pp. 291–311.
Springer (2006)
61. Heydemann, M. C., Meyer, J. C., Sotteau, D.: On forwarding indices of networks. Discrete
Applied Mathematics 23, 103–123 (1989)
62. Holmberg, K., R
¨
onnqvist, M., Yuan, D.: An exact algorithm for the capacitated facility lo-
cation problems with single sourcing. European Journal of Operational Research 113(3),
544–559 (1999)
63. Hromkovic, J., Klasing, R., Monien, B., Peine, R.: Dissemination of information in intercon-
nection networks (broadcasting and gossiping) (1996)
64. ILOG: CPLEX version 11.1 (2008). http://www.ilog.com/products/cplex
65. Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica
4(4), 373–395 (1984)
66. Karp, R. M.: Reducibility among combinatorial problems. In: R. E. Miller, J. W. Thatcher
(eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)
67. Klee, V., Minty, G. J.: How good is the Simplex algorithm? In: O. Shisha (ed.) Inequalities,
III, pp. 159–175. Academic Press, New York, NY (1972)
1 Graphs and Algorithms in Communication Networks on Seven League Boots 59
68. Koch, T., Martin, A., Voß, S.: SteinLib: An updated library on Steiner tree problems in graphs.
Tech. Rep. ZIB-Report 00-37, Konrad-Zuse-Zentrum f
¨
ur Informationstechnik Berlin, Takustr.
7, Berlin (2000). URL http://elib.zib.de/steinlib
69. Kruskal Jr., J. B.: On the shortest spanning tree of a graph and the traveling salesman problem.
Proceedings of the American Mathematical Society 7, 48–50 (1956)
70. LEMON: A C++ Library for Efficient Modelling and Optimization in Networks.
http://lemon.cs.elte.hu
71. Lindberg, P.: Network optimisation with successive smooth approximation. In: 11th Nordic
Teletraffic Seminar. Stockholm (1993)
72. Lynch, N.: Distributed Algorithms. Morgan Kaufmann Publishers (1996)
73. Marsden, G., Marchand, P., Harvey, P., Esener, S.: Optical transpose interconnection system
architectures. OSA Optics Letters 18(13), 1083–1085 (1993)
74. Martello, S., Toth, P.: Knapsack Problems – Algorithms and Computer Implementations.
Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons
(1990). URL http://www.or.deis.unibo.it/kp.html
75. Metzger, B. H.: Spectrum management technique (Fall 1970). Presentation at 38th National
ORSA meeting (Detroit, MI)
76. Nemhauser, G. L., Wolsey, L. A.: Integer and Combinatorial Optimization. Wiley, N. Y. (1988)
77. Orlowski, S., Pi
´
oro, M., Tomaszewski, A., Wess
¨
aly, R.: SNDlib 1.0–Survivable Network De-
sign Library. In: Proceedings of International Network Optimization Conference (INOC2007)
(2007). http://sndlib.zib.de
78. Peleg, D.: Distributed Computing – A Locality-Sensitive Approach. Monographs in Discrete
Mathematics and Applications. SIAM (2000)
79. Pi
´
oro, M., Medhi, D.: Routing, Flow, and Capacity Design in Communication and Computer
Networks. Morgan Kaufmann (2004)
80. Polzin, T.: Algorithms for the Steiner problem in networks. Ph.D. thesis, Universit
¨
at des
Saarlandes (2003)
81. Prim, R. C.: Shortest connection networks and some generalizations. The Bell System Tech-
nical Journal 36, 1389–1401 (1957)
82. Schrijver, A.: Theory of linear and integer programming. Wiley, New York (1986)
83. Schrijver, A.: Combinatorial Optimization – Polyhedra and Efficiency. No. 24 in Algorithms
and Combinatorics. Springer (2003)
84. Sleator, D. D., Tarjan, R. E.: Amortized efficiency of list update and paging rules. Communi-
cations of the ACM 28(2), 202–208 (1985)
85. Stidsen, T., Petersen, B., Rasmussen, K. B., Spoorendonk, S., Zachariasen, M., Rambach, F.,
Kiese, M.: Optimal routing with single backup path protection. In: Proceedings International
Network Optimization Conference (INOC 2007). Spa, Belgium (2007)
86. Suurballe, J. W.: Disjoint paths in a network. Networks 4(2), 125–145 (1974)
87. Tel, G.: Introduction to Distributed Algorithms. Cambridge University Press (1994)
88. Vanderbei, R. J.: Linear Programming: Foundations and Extensions, International Series in
Operations Research & Management Science, vol. 114, 3 edn. Springer-Verlag (2008)
89. Vo
¨
s, S.: Steiner tree problems in telecommunications. In: M. G. C. Resende, P. M. Pardalos
(eds.) Handbook of Optimization in Telecommunications, chap. 18, pp. 459–515. Springer
(2006)
90. Wess
¨
aly, R.: DImensioning Survivable Capacitated NETworks. Ph.D. thesis, Technische Uni-
versit
¨
at Berlin (2000)
91. West, D. B.: Introduction to Graph Theory, 2 edn. Prentice Hall (2001)
92. Wolsey, L. A.: Integer Programming. Series in Discrete Mathematics and Optimization.
Wiley-Interscience (1998)
93. Zymolka, A.: Design of survivable optical networks by mathematical optimization. Ph.d.
thesis, TU Berlin (2007)
94. Zymolka, A., Koster, A. M. C. A., Wess
¨
aly, R.: Transparent optical network design with sparse
wavelength conversion. In: Proceedings of ONDM 2003, pp. 61–80. The 7th IFIP Working
Conference on Optical Network Design & Modelling, Budapest, Hungary (2003)
Part II
Studies in Wireless
and Ad Hoc Networks