Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Drawing Planar Graphs Read chapter Read first chapter

2020 | OriginalPaper | Chapter

Designing Survivable Networks with Zero-Suppressed Binary Decision Diagrams

Authors : Hirofumi Suzuki, Masakazu Ishihata, Shin-ichi Minato

Published in: WALCOM: Algorithms and Computation

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Various network systems such as communication networks require survivability that is tolerance of attacks, failures, and accidents. Designing a network with high survivability is formulated as a survivable network design problem (SNDP). The input of the SNDP is a pair of an edge-weighted graph and a requirement of topology and survivability. For an edge subset of the graph, if it satisfies the requirement, we call it a desired edge subset (DES). The output of the SNDP is the minimum weight DES. Although the SNDP is an optimization problem, to simply solve it is not always desired in terms of the practical use: Designers sometimes want to test multiple DESs including non-optimal DESs, because the theoretical optimal DES is not always the practical best.
In this paper, instead of the optimization, we propose a method to enumerate all DESs with a compact data structure, called the zero-suppressed binary decision diagram (ZDD). Obtained ZDDs support practical network design by performing optimization, sampling, and filtering of DESs. The proposed method combines two typical techniques constructing ZDDs, called the frontier-based search (FBS) and the family algebra, and includes a novel operation on ZDDs. We demonstrate that our method works on various real-world instances of practical scales.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Matching Random Colored Points with Rectangles
next chapter Approximability of the Independent Feedback Vertex Set Problem for Bipartite Graphs
Footnotes
1
Although our approach can handle both directed and undirected graphs, we describe only the undirected version (i.e., \(E \subseteq \{\{u,v\} \mid u,v \in V\}\)) in this paper.
 
Literature
1.
Ellison, R., Linger, R., Longstaff, T., Mead, N.: Survivable network system analysis: a case study. IEEE Software 16, 70–77 (1999)CrossRef
2.
3.
Akgün, I.: New formulations for the hop-constrained minimum spanning tree problem via sherali and driscoll’s tightened miller-tucker-zemlin constraints. Comput. Oper. Res. 38(1), 277–286 (2011)MathSciNetCrossRef
4.
Diarrassouba, I., Gabrel, V., Ridha Mahjoub, A., Gouveia, L., Pesneau, P.: Integer programming formulations for the k-edge-connected 3-hop-constrained network design problem. Networks 67, 148–169 (2015)MathSciNetCrossRef
5.
Fortz, B.: Design of survivable networks with bounded rings. In: Network Theory and Applications (2000)
6.
Gouveia, L., Simonetti, L., Uchoa, E.: Modeling hop-constrained and diameter-constrained minimum spanning tree problems as steiner tree problems over layered graphs. Math. Program. 128(1), 123–148 (2011)MathSciNetCrossRef
7.
Rodriguez-Martin, I., Salazar Gonzlez, J.J., Yaman, H.: The ring/\(\kappa \)-rings network design problem: model and branch-and-cut algorithm. Networks 68, 130–140 (2016)MathSciNetCrossRef
8.
Penttinen, A.: Chapter 10 - Network planning and dimensioning. Lecture Notes: S-38.145 - Introduction to Teletraffic Theory. Helsinki University of Technology (1999)
9.
Minato, S.: Zero-suppressed BDDS for set manipulation in combinatorial problems. In: DAC, pp. 272–277 (1993)
10.
Knuth, D.E.: The Art of Computer Programming: Bitwise tricks & Techniques. Binary Decision Diagrams, vol. 4, fascicle 1. Addison-Wesley Professional, Boston (2009)
11.
Kawahara, J., Inoue, T., Iwashita, H., Minato, S.: Frontier-based search for enumerating all constrained subgraphs with compressed representation. IEICE Trans. Fundam. E100–A(9), 1773–1784 (2017)CrossRef
12.
Coudert, O.: Solving graph optimization problems with ZBDDS. In: Proceedings of the 1997 European Conference on Design and Test, EDTC 1997, p. 224 (1997)
13.
Kawahara, J., Horiyama, T., Hotta, K., Minato, S.I.: Generating all patterns of graph partitions within a disparity bound. In: WALCOM: Algorithms and Computation, pp. 119–131 (2017)CrossRef
14.
Kawahara, J., Saitoh, T., Suzuki, H., Yoshinaka, R.: Solving the longest oneway-ticket problem and enumerating letter graphs by augmenting the two representative approaches with ZDDs. In: Phon-Amnuaisuk, S., Au, T.-W., Omar, S. (eds.) CIIS 2016. AISC, vol. 532, pp. 294–305. Springer, Cham (2017). https://​doi.​org/​10.​1007/​978-3-319-48517-1_​26CrossRef
15.
Minato, S., Ishiura, N., Yajima, S.: Shared binary decision diagram with attributed edges for efficient boolean function manipulation. In: 27th ACM/IEEE Design Automation Conference, pp. 52–57 (1990)
16.
Amarilli, A., Bourhis, P., Jachiet, L., Mengel, S.: A circuit-based approach to efficient enumeration. In: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), vol. 80, pp. 111:1–111:15 (2017)
17.
Yoshinaka, R., Kawahara, J., Denzumi, S., Arimura, H., Ichi-Minato, S.: Counterexamples to the long-standing conjecture on the complexity of BDD binary operations. Inf. Process. Lett. 112, 636–640 (2012)MathSciNetCrossRef
Metadata
Title
Designing Survivable Networks with Zero-Suppressed Binary Decision Diagrams
Authors
Hirofumi Suzuki
Masakazu Ishihata
Shin-ichi Minato
Copyright Year
2020
Book
WALCOM: Algorithms and Computation

Print ISBN: 978-3-030-39880-4

Electronic ISBN: 978-3-030-39881-1

Copyright Year: 2020

DOI
https://doi.org/10.1007/978-3-030-39881-1_23

Premium Partner

    Image Credits