Editing Component (graph theory) (section)

==References==
{{reflist|refs=

<ref name=1look>{{citation
 | last1 = Clark
 | first1 = John
 | last2 = Holton
 | first2 = Derek Allan
 | isbn = 9788170234630
 | page = 28
 | publisher = Allied Publishers
 | title = A First Look at Graph Theory
 | url = https://books.google.com/books?id=kb-aLlgYZuEC&pg=PA28
 | year = 1995
 | access-date = 2022-01-07
 | archive-date = 2022-01-08
 | archive-url = https://web.archive.org/web/20220108225127/https://books.google.com/books?id=kb-aLlgYZuEC&pg=PA28
 | url-status = live
 }}</ref>

<ref name=bengalloun>{{citation
 | last = Bengelloun | first = Safwan Abdelmajid
 | date = December 1982
 | id = {{ProQuest|303248045}}
 | page = 12
 | publisher = Yale University
 | title = Aspects of Incremental Computing
 | type = PhD thesis}}</ref>

<ref name=berge>{{citation
 | last = Berge | first = Claude | author-link = Claude Berge
 | journal = [[Comptes rendus de l'Académie des Sciences|Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences]]
 | mr = 100850
 | pages = 258–259
 | title = Sur le couplage maximum d'un graphe
 | volume = 247
 | year = 1958}}</ref>

<ref name=berkramal>{{citation
 | last1 = Berenbrink | first1 = Petra
 | last2 = Krayenhoff | first2 = Bruce
 | last3 = Mallmann-Trenn | first3 = Frederik
 | doi = 10.1016/j.ipl.2014.05.008
 | issue = 11
 | journal = [[Information Processing Letters]]
 | mr = 3230913
 | pages = 639–642
 | title = Estimating the number of connected components in sublinear time
 | volume = 114
 | year = 2014}}</ref>

<ref name=bollobas>{{citation
 | last = Bollobás
 | first = Béla
 | author-link = Béla Bollobás
 | doi = 10.1007/978-1-4612-0619-4
 | isbn = 0-387-98488-7
 | mr = 1633290
 | page = 6
 | publisher = Springer-Verlag
 | location = New York
 | series = Graduate Texts in Mathematics
 | title = Modern Graph Theory
 | url = https://books.google.com/books?id=JeIlBQAAQBAJ&pg=PA6
 | volume = 184
 | year = 1998
 | access-date = 2022-01-08
 | archive-date = 2022-01-08
 | archive-url = https://web.archive.org/web/20220108192625/https://books.google.com/books?id=JeIlBQAAQBAJ&pg=PA6
 | url-status = live
 }}</ref>

<ref name=boost>{{citation
 | last1 = Siek | first1 = Jeremy
 | last2 = Lee | first2 = Lie-Quan
 | last3 = Lumsdaine | first3 = Andrew
 | contribution = 7.1 Connected components: Definitions
 | pages = 97–98
 | publisher = Addison-Wesley
 | title = The Boost Graph Library: User Guide and Reference Manual
 | year = 2001}}</ref>

<ref name=chvatal>{{citation
 | last = Chvátal | first = Václav | author-link = Václav Chvátal
 | doi = 10.1016/0012-365X(73)90138-6 | doi-access = free
 | issue = 3
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 0316301
 | pages = 215–228
 | title = Tough graphs and Hamiltonian circuits
 | volume = 5
 | year = 1973}}</ref>

<ref name=cioaba>{{citation
 | last = Cioabă | first = Sebastian M.
 | editor-last = Dehmer | editor-first = Matthias
 | contribution = Some applications of eigenvalues of graphs
 | doi = 10.1007/978-0-8176-4789-6_14
 | location = New York
 | mr = 2777924
 | pages = 357–379
 | publisher = Birkhäuser/Springer
 | title = Structural Analysis of Complex Networks
 | year = 2011| isbn = 978-0-8176-4788-9
 }}; see [https://books.google.com/books?id=0ymYdW1rtBUC&pg=PA361 proof of Lemma 5, p. 361] {{Webarchive|url=https://web.archive.org/web/20220108230453/https://books.google.com/books?id=0ymYdW1rtBUC&pg=PA361 |date=2022-01-08 }}</ref>

<ref name=cohav>{{citation
 | last1 = Cohen
 | first1 = Reuven
 | last2 = Havlin
 | first2 = Shlomo
 | contribution = 10.1 Percolation on complex networks: Introduction
 | contribution-url = https://books.google.com/books?id=1ECLiFrKulIC&pg=PA97
 | isbn = 978-1-139-48927-0
 | pages = 97–98
 | publisher = Cambridge University Press
 | title = Complex Networks: Structure, Robustness and Function
 | year = 2010
 | access-date = 2022-01-10
 | archive-date = 2022-01-10
 | archive-url = https://web.archive.org/web/20220110174730/https://books.google.com/books?id=1ECLiFrKulIC&pg=PA97
 | url-status = live
 }}</ref>

<ref name=dst>{{citation
 | last1 = Dillencourt | first1 = Michael B.
 | last2 = Samet | first2 = Hanan | author2-link = Hanan Samet
 | last3 = Tamminen | first3 = Markku
 | doi = 10.1145/128749.128750
 | issue = 2
 | journal = [[Journal of the ACM]]
 | mr = 1160258
 | pages = 253–280
 | title = A general approach to connected-component labeling for arbitrary image representations
 | volume = 39
 | year = 1992| s2cid = 1869184
 | citeseerx = 10.1.1.73.8846
 }}</ref>

<ref name=foldes>{{citation
 | last = Foldes
 | first = Stephan
 | isbn = 978-1-118-03143-8
 | page = 199
 | publisher = John Wiley & Sons
 | title = Fundamental Structures of Algebra and Discrete Mathematics
 | url = https://books.google.com/books?id=A59RivXPMzkC&pg=PA199
 | year = 2011
 | access-date = 2022-01-07
 | archive-date = 2022-01-07
 | archive-url = https://web.archive.org/web/20220107080529/https://books.google.com/books?id=A59RivXPMzkC&pg=PA199
 | url-status = live
 }}</ref>

<ref name=frikar>{{citation
 | last1 = Frieze | first1 = Alan | author1-link = Alan M. Frieze
 | last2 = Karoński | first2 = Michał
 | contribution = 1.1 Models and relationships
 | doi = 10.1017/CBO9781316339831
 | isbn = 978-1-107-11850-8
 | mr = 3675279
 | pages = 3–9
 | publisher = Cambridge University Press, Cambridge
 | title = Introduction to Random Graphs
 | year = 2016}}</ref>

<ref name=subcritical>{{harvtxt|Frieze|Karoński|2016}}, 2.1 Sub-critical phase, pp. 20–33; see especially Theorem 2.8, p. 26, Theorem 2.9, p. 28, and Lemma 2.11, p. 29</ref>

<ref name=supercritical>{{harvtxt|Frieze|Karoński|2016}}, 2.2 Super-critical phase, pp. 33; see especially Theorem 2.14, p. 33–39</ref>

<ref name=critical>{{harvtxt|Frieze|Karoński|2016}}, 2.3 Phase transition, pp. 39–45</ref>

<ref name=random-connectivity>{{harvtxt|Frieze|Karoński|2016}}, 4.1 Connectivity, pp. 64–68</ref>

<ref name=hhkp>{{citation
 | last1 = Huang | first1 = Shang-En
 | last2 = Huang | first2 = Dawei
 | last3 = Kopelowitz | first3 = Tsvi
 | last4 = Pettie | first4 = Seth
 | editor-last = Klein | editor-first = Philip N.
 | arxiv = 1609.05867
 | contribution = Fully dynamic connectivity in <math>O\bigl(\log n(\log\log n)^2\bigr)</math> amortized expected time
 | doi = 10.1137/1.9781611974782.32
 | pages = 510–520
 | title = Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19
 | year = 2017| s2cid = 15585534
 }}</ref>

<ref name=hoptar>{{citation
 | last1 = Hopcroft | first1 = John | author1-link = John Hopcroft
 | last2 = Tarjan | first2 = Robert | author2-link = Robert Tarjan
 | date = June 1973
 | doi = 10.1145/362248.362272
 | issue = 6
 | journal = [[Communications of the ACM]]
 | pages = 372–378
 | title = Algorithm 447: efficient algorithms for graph manipulation
 | volume = 16| s2cid = 14772567 | doi-access = free
 }}</ref>

<ref name=jnp>{{citation
 | last1 = Joyner
 | first1 = David
 | last2 = Nguyen
 | first2 = Minh Van
 | last3 = Phillips
 | first3 = David
 | contribution = 1.6.1 Union, intersection, and join
 | contribution-url = https://code.google.com/p/graphbook/
 | date = May 10, 2013
 | edition = 0.8-r1991
 | pages = 34–35
 | publisher = Google
 | title = Algorithmic Graph Theory and Sage
 | access-date = January 8, 2022
 | archive-date = January 16, 2016
 | archive-url = https://web.archive.org/web/20160116090036/https://code.google.com/p/graphbook/
 | url-status = live
 }}</ref>

<ref name=knuth>{{citation
 | last = Knuth
 | first = Donald E.
 | author-link = Donald Knuth
 | contribution = Weak components
 | date = January 15, 2022
 | pages = 11–14
 | title = The Art of Computer Programming, Volume 4, Pre-Fascicle 12A: Components and Traversal
 | url = https://cs.stanford.edu/~knuth/fasc12a+.pdf
 | access-date = March 1, 2022
 | archive-date = January 18, 2022
 | archive-url = https://web.archive.org/web/20220118183018/https://cs.stanford.edu/~knuth/fasc12a+.pdf
 | url-status = live
 }}</ref>

<ref name=kozen>{{citation
 | last = Kozen
 | first = Dexter C.
 | author-link = Dexter Kozen
 | contribution = 4.1 Biconnected components
 | contribution-url = https://books.google.com/books?id=HFn1BwAAQBAJ&pg=PA20
 | doi = 10.1007/978-1-4612-4400-4
 | isbn = 0-387-97687-6
 | mr = 1139767
 | pages = 20–22
 | publisher = Springer-Verlag
 | location = New York
 | series = Texts and Monographs in Computer Science
 | title = The Design and Analysis of Algorithms
 | year = 1992
 | s2cid = 27747202
 | access-date = 2022-01-08
 | archive-date = 2022-01-08
 | archive-url = https://web.archive.org/web/20220108192351/https://books.google.com/books?id=HFn1BwAAQBAJ&pg=PA20
 | url-status = live
 }}</ref>

<ref name=lewpap>{{citation
 | last1 = Lewis | first1 = Harry R. | author1-link = Harry R. Lewis
 | last2 = Papadimitriou | first2 = Christos H. | author2-link = Christos Papadimitriou
 | doi = 10.1016/0304-3975(82)90058-5
 | issue = 2
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | mr = 666539
 | pages = 161–187
 | title = Symmetric space-bounded computation
 | volume = 19
 | year = 1982| doi-access = free
 }}</ref>

<ref name=lewzax>{{citation
 | last1 = Lewis
 | first1 = Harry
 | author1-link = Harry R. Lewis
 | last2 = Zax
 | first2 = Rachel
 | isbn = 978-0-691-19061-7
 | page = 145
 | publisher = Princeton University Press
 | title = Essential Discrete Mathematics for Computer Science
 | url = https://books.google.com/books?id=fAZ-DwAAQBAJ&pg=PA145
 | year = 2019
 | access-date = 2022-01-08
 | archive-date = 2022-01-08
 | archive-url = https://web.archive.org/web/20220108191703/https://books.google.com/books?id=fAZ-DwAAQBAJ&pg=PA145
 | url-status = live
 }}</ref>

<ref name=mcnosh>{{citation
 | last1 = McColl | first1 = W. F.
 | last2 = Noshita | first2 = K.
 | doi = 10.1016/0166-218X(86)90020-X
 | issue = 1
 | journal = [[Discrete Applied Mathematics]]
 | mr = 856101
 | pages = 67–73
 | title = On the number of edges in the transitive closure of a graph
 | volume = 15
 | year = 1986| doi-access = 
 }}</ref>

<ref name=read>{{citation
 | last = Read | first = Ronald C. | author-link = Ronald C. Read
 | doi = 10.1016/S0021-9800(68)80087-0
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 224505
 | pages = 52–71
 | title = An introduction to chromatic polynomials
 | volume = 4
 | year = 1968| doi-access = free
 }}; see Theorem 2, p. 59, and corollary, p. 65</ref>

<ref name=reingold>{{citation
 | last = Reingold | first = Omer | author-link = Omer Reingold
 | doi = 10.1145/1391289.1391291 | doi-access = 
 | issue = 4
 | journal = [[Journal of the ACM]]
 | mr = 2445014
 | page = A17:1–A17:24
 | title = Undirected connectivity in log-space
 | volume = 55
 | year = 2008| s2cid = 207168478 }}</ref>

<ref name=skiena>{{citation
 | last = Skiena
 | first = Steven
 | author-link = Steven Skiena
 | contribution = 6.1.2 Kruskal's Algorithm
 | contribution-url = https://books.google.com/books?id=7XUSn0IKQEgC&pg=PA196
 | doi = 10.1007/978-1-84800-070-4
 | isbn = 978-1-84800-069-8
 | pages = 196–198
 | publisher = Springer
 | title = The Algorithm Design Manual
 | year = 2008
 | bibcode = 2008adm..book.....S
 | access-date = 2022-01-07
 | archive-date = 2022-01-07
 | archive-url = https://web.archive.org/web/20220107183740/https://books.google.com/books?id=7XUSn0IKQEgC&pg=PA196
 | url-status = live
 }}</ref>

<ref name=thuswa>{{citation
 | last1 = Thulasiraman
 | first1 = K.
 | last2 = Swamy
 | first2 = M. N. S.
 | isbn = 978-1-118-03025-7
 | page = 9
 | publisher = John Wiley & Sons
 | title = Graphs: Theory and Algorithms
 | url = https://books.google.com/books?id=rFH7eQffQNkC&pg=PA9
 | year = 2011
 | access-date = 2022-01-07
 | archive-date = 2022-01-07
 | archive-url = https://web.archive.org/web/20220107215533/https://books.google.com/books?id=rFH7eQffQNkC&pg=PA9
 | url-status = live
 }}</ref>

<ref name=tutte-betti>{{citation
 | last = Tutte
 | first = W. T.
 | author-link = W. T. Tutte
 | isbn = 0-201-13520-5
 | mr = 746795
 | page = 15
 | publisher = Addison-Wesley
 | location = Reading, Massachusetts
 | series = Encyclopedia of Mathematics and its Applications
 | title = Graph Theory
 | url = https://books.google.com/books?id=uTGhooU37h4C&pg=PA15
 | volume = 21
 | year = 1984
 | access-date = 2022-01-07
 | archive-date = 2022-01-07
 | archive-url = https://web.archive.org/web/20220107081347/https://books.google.com/books?id=uTGhooU37h4C&pg=PA15
 | url-status = live
 }}</ref>

<ref name=tutte-matching>{{citation
 | last = Tutte | first = W. T. | author-link = W. T. Tutte
 | doi = 10.1112/jlms/s1-22.2.107
 | journal = [[The Journal of the London Mathematical Society]]
 | mr = 23048
 | pages = 107–111
 | title = The factorization of linear graphs
 | volume = 22
 | year = 1947| issue = 2 }}</ref>

<ref name=wilson>{{citation
 | last = Wilson | first = R. J. | author-link = Robin Wilson (mathematician)
 | doi = 10.1080/00029890.1973.11993318
 | journal = [[The American Mathematical Monthly]]
 | jstor = 2319608
 | mr = 371694
 | pages = 500–525
 | title = An introduction to matroid theory
 | volume = 80
 | year = 1973| issue = 5 }}</ref>

<ref name=wood>{{citation
 | last = Wood
 | first = David R.
 | author-link = David Wood (mathematician)
 | editor-last = Kao
 | editor-first = Ming-Yang
 | contribution = Three-dimensional graph drawing
 | doi = 10.1007/978-3-642-27848-8_656-1
 | pages = 1–7
 | publisher = Springer
 | title = Encyclopedia of Algorithms
 | url = https://users.monash.edu/~davidwo/papers/EncPaper.pdf
 | year = 2014
 | isbn = 978-3-642-27848-8
 | access-date = 2022-01-08
 | archive-date = 2022-01-08
 | archive-url = https://web.archive.org/web/20220108225308/https://users.monash.edu/~davidwo/papers/EncPaper.pdf
 | url-status = live
 }}</ref>

<ref name=wulff-nilsen>{{citation
 | last = Wulff-Nilsen | first = Christian
 | editor-last = Khanna | editor-first = Sanjeev
 | arxiv = 1209.5608
 | contribution = Faster deterministic fully-dynamic graph connectivity
 | doi = 10.1137/1.9781611973105.126
 | pages = 1757–1769
 | title = Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013
 | year = 2013| isbn = 978-1-61197-251-1
 | s2cid = 13397958
 }}</ref>

}}