Top

Published in:

2024 | OriginalPaper | Chapter

Graphic Approximation of Integer Sequences

Author : Brian Cloteaux

Published in: Combinatorics, Graph Theory and Computing

Publisher: Springer Nature Switzerland

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

search-config

AI-assisted search

Off

Abstract

A variety of network modeling problems begin by generating a degree sequence drawn from a given probability distribution. If the randomly generated sequence is not graphic, we give two new approaches for generating a graphic approximation of the sequence. These schemes are fast, simple to implement, and only require a linear amount of memory. This allows approximation to be performed on very large integer sequences.

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 j-Multiple, k-Component Order Neighbor Connectivity

next chapter Changing the Uniform Spectrum by Deleting Edges

Arikati, S.R., Maheshwari, A.: Realizing degree sequences in parallel. SIAM J. Discrete Math. 9(2), 317–338 (1996). https://doi.org/10.1137/S0895480194267932MathSciNetCrossRef

Brylawski, T.: The lattice of integer partitions. Discrete Math. 6, 201–219 (1973). https://doi.org/10.1016/0012-365X(73)90094-0MathSciNetCrossRef

Chen, Y.C.: A short proof of Kundu’s k-factor theorem. Discrete Math. 71(2), 177–179 (1988). http://dx.doi.org/10.1016/0012-365X(88)90070-2MathSciNetCrossRef

Cloteaux, B.: Is this for real? Fast graphicality testing. Computing in Science & Engineering 17(6), 91–95 (2015). https://doi.org/10.1109/MCSE.2015.125

Erdős, P., Gallai, T.: Graphs with prescribed degrees of vertices. Mat. Lapok 11, 264–274 (1960), Hungarian

Hagberg, A.A., Schult, D.A., Swart, P.J.: Exploring network structure, dynamics, and function using NetworkX. In: Proceedings of the 7th Python in Science Conference (SciPy2008). pp. 11–15. Pasadena, CA USA (Aug 2008)

Hell, P., Kirkpatrick, D.: Linear-time certifying algorithms for near-graphical sequences. Discrete Math. 309(18), 5703–5713 (2009). https://doi.org/10.1016/j.disc.2008.05.005MathSciNetCrossRef

Mahadev, N., Peled, U.: Threshold Graphs and Related Topics. North Holland (1995), Annals of Discrete Mathematics 56

Mihail, M., Vishnoi, N.: On generating graphs with prescribed degree sequences for complex network modeling applications. In: Proceedings of the 3rd Workshop on Approximation and Randomization Algorithms in Communication Networks (ARACNE). pp. 1–11 (2002)

10.

Muirhead, R.F.: Some methods applicable to identities and inequalities of symmetric algebraic functions of n letters. Proceedings of the Edinburgh Mathematical Society 21, 144–157 (1903)CrossRef

11.

Pittel, B.: Confirming two conjectures about the integer partitions. Journal of Combinatorial Theory, Series A 88(1), 123–135 (Oct 1999). https://doi.org/10.1006/jcta.1999.2986MathSciNetCrossRef

12.

Ruch, E., Gutman, I.: The branching extent of graphs. Journal of Combinatorics, Information, & System Sciences 4(4), 285–295 (1979)MathSciNet

13.

Zverovich, I., Zverovich, V.: Contributions to the theory of graphic sequences. Discrete Mathematics 105(1-3), 293–303 (1992). https://doi.org/10.1016/0012-365X(92)90152-6MathSciNetCrossRef

Title: Graphic Approximation of Integer Sequences
Author: Brian Cloteaux
Publisher: Springer Nature Switzerland
Book: Combinatorics, Graph Theory and Computing
Print ISBN: 978-3-031-62165-9

Electronic ISBN: 978-3-031-62166-6

Copyright Year: 2024
DOI: https://doi.org/10.1007/978-3-031-62166-6_13

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"