Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Buchtitelbild

2021 | OriginalPaper | Buchkapitel

Relaxed and Approximate Graph Realizations

verfasst von : Amotz Bar-Noy, Toni Böhnlein, David Peleg, Mor Perry, Dror Rawitz

Erschienen in: Combinatorial Algorithms

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

A network realization problem involves a given specification \(\pi \) for some network parameters (such as vertex degrees or inter-vertex distances), and requires constructing a network G that satisfies \(\pi \), if possible. In many settings, it may be difficult or impossible to come up with a precise realization (e.g., the specification data might be inaccurate, or the reconstruction problem might be computationally infeasible). In this expository paper, we review various alternative approaches for coping with these difficulties by relaxing the requirements, discuss the resulting problems and illustrate some (precise or approximate) solutions.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Nächstes Kapitel Search for Combinatorial Objects Using Lattice Algorithms – Revisited
Literatur
1.
2.
3.
Alpers, A., Gritzmann, P.: Reconstructing binary matrices under window constraints from their row and column sums. Fundamenta Informaticae 155(4), 321–340 (2017)MathSciNetMATHCrossRef
4.
Alpers, A., Gritzmann, P.: Dynamic discrete tomography. Inverse Probl. 34(3), 034003 (2018)
5.
6.
7.
8.
9.
Baldisserri, A.: Buneman’s theorem for trees with exactly n vertices. CoRR (2014)
10.
11.
Bar-Noy, A., Böhnlein, T., Lotker, Z., Peleg, D., Rawitz, D.: The generalized microscopic image reconstruction problem. In: 30th ISAAC, volume 149 of LIPIcs, pp. 42:1–42:15 (2019)
12.
Bar-Noy, A., Choudhary, K., Peleg, D., Rawitz, D.: Efficiently realizing interval sequences. SIAM J. Discr. Math. 34(4), 2318–2337 (2020)MathSciNetMATHCrossRef
13.
Bar-Noy, A., Peleg, D., Perry, M., Rawitz, D.: Composed degree-distance realizations of graphs. In: 32nd IWOCA (2021)
14.
Bar-Noy, A., Peleg, D., Perry, M., Rawitz, D., Schwartz, N. L.: Distance realization approximations. In: preparation (2021)
15.
Battaglino, D., Frosini, A., Rinaldi, S.: A decomposition theorem for homogeneous sets with respect to diamond probes. Comput. Vis. Image Underst. 117, 319–325 (2013)CrossRef
16.
Baum, D.A., Smith, S.D.: Tree Thinking: an Introduction to Phylogenetic Biology. Roberts and Company, Greenwood Village, CO (2013)
17.
Blitzstein, J.K., Diaconis, P.: A sequential importance sampling algorithm for generating random graphs with prescribed degrees. Internet Math. 6(4), 489–522 (2011)MathSciNetMATHCrossRef
18.
Broom, M., Cannings, C.: A dynamic network population model with strategic link formation governed by individual preferences. J. Theoret. Biol. 335, 160–168 (2013)MathSciNetMATHCrossRef
19.
20.
Broom, M., Cannings, C.: Game theoretical modelling of a dynamically evolving network i: general target sequences. J. Dyn. Games 335, 285–318 (2017)MathSciNetMATHCrossRef
21.
Burstein, D., Rubin, J.: Sufficient conditions for graphicality of bidegree sequences. SIAM J. Discr. Math. 31, 50–62 (2017)MathSciNetMATHCrossRef
22.
Cai, M.-C., Deng, X., Zang, W.: Solution to a problem on degree sequences of graphs. Discr. Math. 219(1–3), 253–257 (2000)MathSciNetMATHCrossRef
23.
Camin, J.H., Sokal, R.R.: A method for deducing branching sequences in phylogeny. Evolution 19, 311–326 (1965)CrossRef
24.
25.
Chernyak, A.A., Chernyak, Z.A., Tyshkevich, R.I.: On forcibly hereditary \(p\)-graphical sequences. Discr. Math. 64, 111–128 (1987)MathSciNetMATHCrossRef
26.
W. Chou and H. Frank. Survivable communication networks and the terminal capacity matrix. IEEE Trans. Circ. Theory, CT-17, 192–197 (1970)
27.
Choudum, S.A.: A simple proof of the Erdös-Gallai theorem on graph sequences. Bull. Austral. Math. Soc. 33(1), 67–70 (1991)MathSciNetCrossRef
28.
Chung, F.R.K., Garrett, M.W., Graham, R.L., Shallcross, D.: Distance realization problems with applications to internet tomography. J. Comput. Syst. Sci. 63, 432–448 (2001)MathSciNetMATHCrossRef
29.
30.
31.
Culberson, J.C., Rudnicki, P.: A fast algorithm for constructing trees from distance matrices. Inf. Process. Lett. 30(4), 215–220 (1989)MathSciNetMATHCrossRef
32.
33.
34.
Dress, A.W.M.: Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces. Adv. Math. 53, 321–402 (1984)MathSciNetMATHCrossRef
35.
Erdös, D., Gemulla, R., Terzi, E.: Reconstructing graphs from neighborhood data. ACM Trans. Knowl. Discov. Data 8(4), 23:1–23:22 (2014)
36.
Erdös, P., Gallai, T.: Graphs with prescribed degrees of vertices [Hungarian]. Matematikai Lapok 11, 264–274 (1960)MATH
37.
Erdös, P.L., Miklós, I., Toroczkai, Z.: A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs. Electr. J. Comb. 17(1) (2010)
38.
Even, G., Medina, M., Patt-Shamir, B.: On-line path computation and function placement in SDNs. Theory Comput. Syst. 63(2), 306–325 (2019)MathSciNetMATHCrossRef
39.
40.
41.
Felsenstein, J.: Evolutionary trees from DNA sequences: a maximum likelihood approach. J. Mol. Evol. 17, 368–376 (1981)CrossRef
42.
Fitch, W.M.: Toward defining the course of evolution: Minimum change for a specific tree topology. Syst. Biol. 20, 406–416 (1971)CrossRef
43.
44.
Frank, A.: Connectivity augmentation problems in network design. In: Mathematical programming: state of the art, pp. 34–63. Univ. Michigan (1994)
45.
Frank, H., Chou, W.: Connectivity considerations in the design of survivable networks. IEEE Trans. Circuit Theory, CT-17, 486–490 (1970)
46.
Frosini, A., Nivat, M.: Binary matrices under the microscope: a tomographical problem. Theor. Comput. Sci. 370(1–3), 201–217 (2007)MathSciNetMATHCrossRef
47.
Frosini, A., Nivat, M., Rinaldi, S.: Scanning integer matrices by means of two rectangular windows. Theor. Comput. Sci. 406(1–2), 90–96 (2008)MathSciNetMATHCrossRef
48.
49.
50.
Garg, A., Goel, A., Tripathi, A.: Constructive extensions of two results on graphic sequences. Discr. Appl. Math. 159(17), 2170–2174 (2011)MathSciNetMATHCrossRef
51.
Gontier, N.: Depicting the tree of life: the philosophical and historical roots of evolutionary tree diagrams. Evol. Educ. Outreach 4, 515–538 (2011)CrossRef
52.
Gritzmann, P., Langfeld, B., Wiegelmann, M.: Uniqueness in discrete tomography: three remarks and a corollary. SIAM J. Discr. Math. 25, 1589–1599 (2011)MathSciNetMATHCrossRef
53.
Guo, J., Yin, J.: A variant of Niessen’s problem on degree sequences of graphs. Discr. Math. Theor. Comput. Sci. 16, 287–292 (2014)MathSciNetMATH
54.
Gupta, G., Joshi, P., Tripathi, A.: Graphic sequences of trees and a problem of Frobenius. Czechoslovak Math. J. 57, 49–52 (2007)MathSciNetMATHCrossRef
55.
Hakimi, S.L.: On realizability of a set of integers as degrees of the vertices of a linear graph -I. SIAM J. Appl. Math. 10(3), 496–506 (1962)MathSciNetMATHCrossRef
56.
57.
58.
59.
Hartung, S., Nichterlein, A.: Np-hardness and fixed-parameter tractability of realizing degree sequences with directed acyclic graphs. SIAM J. Discr. Math. 29, 1931–1960 (2015)MathSciNetMATHCrossRef
60.
Havel, V.: A remark on the existence of finite graphs [in Czech]. Casopis Pest. Mat. 80, 477–480 (1955)MATHCrossRef
61.
Heinrich, K., Hell, P., Kirkpatrick, D.G., Liu, G.: A simple existence criterion for \((g < f)\)-factors. Discr. Math. 85, 313–317 (1990)
62.
Hell, P., Kirkpatrick, D.: Linear-time certifying algorithms for near-graphical sequences. Discr. Math. 309(18), 5703–5713 (2009)MathSciNetMATHCrossRef
63.
Hennig, W.: Phylogenetic Systematics. Illinois University Press, Champaign (1966)
64.
Herman, G.T., Kuba, A.: Discrete Tomography: Foundations, Algorithms, and Applications. Springer Science & Business Media (2012)
65.
Hulett, H., Will, T.G., Woeginger, G.J.: Multigraph realizations of degree sequences: maximization is easy, minimization is hard. Oper. Res. Lett. 36(5), 594–596 (2008)MathSciNetMATHCrossRef
66.
Jayadev, S.P., Narasimhan, S., Bhatt, N.: Learning conserved networks from flows. Technical report, CoRR (2019). http://​arxiv.​org/​abs/​1905.​08716
67.
68.
Kidd, K.K., Sgaramella-Zonta, L.: Phylogenetic analysis: Concepts and methods. American J. Hum. Gen. 23, 235–252 (1971)
69.
Kim, H., Toroczkai, Z., Erdos, P.L., Miklos, I., Szekely, L.A.: Degree-based graph construction. J. Phys. Math. Theor. 42, 1–10 (2009)MathSciNetMATH
70.
Kleitman, D.J.: Minimal number of multiple edges in realization of an incidence sequence without loops. SIAM J. Appl. Math. 18(1), 25–28 (1970)MathSciNetMATHCrossRef
71.
Kleitman, D.J., Wang, D.L.: Algorithms for constructing graphs and digraphs with given valences and factors. Discr. Math. 6, 79–88 (1973)MathSciNetMATHCrossRef
72.
73.
Li, C., McCormick, S., Simchi-Levi, D.: On the minimum-cardinality-bounded-diameter and the bounded-cardinality-minimum-diameter edge addition problems. Oper. Res. Lett. 11, 303–308 (1992)
74.
75.
Mihail, M., Vishnoi, N.: On generating graphs with prescribed degree sequences for complex network modeling applications. In: 3rd ARACNE (2002)
76.
Nieminen, J.: Realizing the distance matrix of a graph. J. Inf. Process. Cybern. 12(1/2), 29–31 (1976)MathSciNetMATH
77.
78.
79.
Owens, A., Trent, H.: On determining minimal singularities for the realizations of an incidence sequence. SIAM J. Appl. Math. 15(2), 406–418 (1967)MathSciNetMATHCrossRef
80.
Owens, A.B.: On determining the minimum number of multiple edges for an incidence sequence. SIAM J. Appl. Math. 18(1), 238–240 (1970)MathSciNetMATHCrossRef
81.
Patrinos, A.N., Hakimi, S.L.: The distance matrix of a graph n and its tree realizability. Q. Appl. Math. 30(3), 255 (1972)
82.
83.
84.
Schuh, R.T., Brower, A.V.: Biological Systematics: Principles and Applications. Cornell University Press (2009)
85.
86.
Simões-Pereira, J.M.S.: An optimality criterion for graph embeddings of metrics. SIAM J. Discr. Math. 1(2), 223–229 (1988)MathSciNetMATHCrossRef
87.
Simões-Pereira, J.M.S.: An algorithm and its role in the study of optimal graph realizations of distance matrices. Discr. Math. 79(3), 299–312 (1990)MathSciNetMATHCrossRef
88.
Swofford, D.L., Olsen, G.J.: Phylogeny reconstruction. Mol. Syst. 411–501 (1990)
89.
Tatsuya, A., Nagamochi, H.: Comparison and enumeration of chemical graphs. Comput. Struct. Biotechnol. 5(6), e201302004 (2013)
90.
91.
Tripathi, A., Venugopalan, S., West, D.B.: A short constructive proof of the Erdös-Gallai characterization of graphic lists. Discr. Math. 310(4), 843–844 (2010)MATHCrossRef
92.
Tripathi, A., Vijay, S.: A note on a theorem of Erdös & Gallai. Discr. Math. 265(1–3), 417–420 (2003)MATHCrossRef
93.
94.
95.
Tyshkevich, R.I., Chernyak, A.A., Chernyak, Z.A.: Graphs and degree sequences: a survey I. Cybernetics 23, 734–745 (1987)MATHCrossRef
96.
97.
Tyshkevich, R.I., Chernyak, A.A., Chernyak, Z.A.: Graphs and degree sequences: a survey III. Cybernetics 24, 539–548 (1988)
98.
Tyshkevich, R.I., Mel’nikov, O.I., Kotov, V.M.: Graphs and degree sequences: canonical decomposition. Cybernetics 17, 722–727 (1981)MATHCrossRef
99.
Ulam, S.: A Collection of Mathematical Problems. Wiley, Hoboken (1960)
100.
101.
102.
Zverovich, I.E., Zverovich, V.E.: Contributions to the theory of graphic sequences. Discr. Math. 105(1–3), 293–303 (1992)MathSciNetMATHCrossRef
Metadaten
Titel
Relaxed and Approximate Graph Realizations
verfasst von
Amotz Bar-Noy
Toni Böhnlein
David Peleg
Mor Perry
Dror Rawitz
Copyright-Jahr
2021
Buch
Combinatorial Algorithms

Print ISBN: 978-3-030-79986-1

Electronic ISBN: 978-3-030-79987-8

Copyright-Jahr: 2021

DOI
https://doi.org/10.1007/978-3-030-79987-8_1