Editing Graphic matroid (section)

==Algorithms==
A minimum weight basis of a graphic matroid is a [[minimum spanning tree]] (or minimum spanning forest, if the underlying graph is disconnected). Algorithms for computing minimum spanning trees have been intensively studied; it is known how to solve the problem in linear randomized expected time in a comparison model of computation,<ref>{{citation
 | last1 = Karger | first1 = David R. | author1-link = David Karger
 | last2 = Klein | first2 = Philip N.
 | last3 = Tarjan | first3 = Robert E. | author3-link = Robert Tarjan
 | doi = 10.1145/201019.201022
 | mr = 1409738
 | issue = 2
 | journal = [[Journal of the Association for Computing Machinery]]
 | pages = 321–328
 | title = A randomized linear-time algorithm to find minimum spanning trees
 | volume = 42
 | year = 1995| doi-access = free
 }}</ref> or in linear time in a model of computation in which the edge weights are small integers and bitwise operations are allowed on their binary representations.<ref>{{citation
 | last1 = Fredman | first1 = M. L. | author1-link = Michael Fredman
 | last2 = Willard | first2 = D. E. | author2-link = Dan Willard
 | doi = 10.1016/S0022-0000(05)80064-9
 | mr = 1279413
 | issue = 3
 | journal = [[Journal of Computer and System Sciences]]
 | pages = 533–551
 | title = Trans-dichotomous algorithms for minimum spanning trees and shortest paths
 | volume = 48
 | year = 1994| doi-access = free
 }}.</ref> The fastest known time bound that has been proven for a deterministic algorithm is slightly superlinear.<ref>{{citation
 | last = Chazelle | first = Bernard | authorlink = Bernard Chazelle
 | doi = 10.1145/355541.355562
 | mr = 1866456
 | issue = 6
 | journal = [[Journal of the Association for Computing Machinery]]
 | pages = 1028–1047
 | title = A minimum spanning tree algorithm with inverse-Ackermann type complexity
 | volume = 47
 | year = 2000| s2cid = 6276962 | doi-access = free
 }}.</ref>

Several authors have investigated algorithms for testing whether a given matroid is graphic.<ref>{{citation
 | last = Tutte | first = W. T. | authorlink = W. T. Tutte
 | journal = [[Proceedings of the American Mathematical Society]]
 | mr = 0117173
 | pages = 905–917
 | title = An algorithm for determining whether a given binary matroid is graphic.
 | volume = 11
 | year = 1960
 | issue = 6 | doi=10.2307/2034435| jstor = 2034435 }}.</ref><ref>{{citation
 | last1 = Bixby | first1 = Robert E.
 | last2 = Cunningham | first2 = William H.
 | doi = 10.1287/moor.5.3.321
 | issue = 3
 | journal = [[Mathematics of Operations Research]]
 | mr = 594849
 | pages = 321–357
 | title = Converting linear programs to network problems
 | volume = 5
 | year = 1980}}.</ref><ref>{{citation
 | last = Seymour | first = P. D. | authorlink = Paul Seymour (mathematician)
 | doi = 10.1007/BF02579179
 | issue = 1
 | journal = Combinatorica
 | mr = 602418
 | pages = 75–78
 | title = Recognizing graphic matroids
 | volume = 1
 | year = 1981| s2cid = 35579707 }}.</ref> For instance, an algorithm of {{harvtxt|Tutte|1960}} solves this problem when the input is known to be a [[binary matroid]]. {{harvtxt|Seymour|1981}} solves this problem for arbitrary matroids given access to the matroid only through an [[matroid oracle|independence oracle]], a subroutine that determines whether or not a given set is independent.