Editing Betweenness problem (section)

{{Short description|Algorithm in order theory}}
{{about|ordering items with constraints|centrality in social networks|betweenness centrality|the betweenness relation in geometry|ordered geometry}}
'''Betweenness''' is an [[algorithmic problem]] in [[order theory]] about ordering a collection of items subject to constraints that some items must be placed between others.<ref name="cs98">{{citation
 | last1 = Chor | first1 = Benny | author1-link = Benny Chor
 | last2 = Sudan | first2 = Madhu | author2-link = Madhu Sudan
 | doi = 10.1137/S0895480195296221
 | issue = 4
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | mr = 1640920
 | pages = 511–523 (electronic)
 | title = A geometric approach to betweenness
 | volume = 11
 | year = 1998}}.</ref> It has applications in [[bioinformatics]]<ref name="sksl97">{{citation
 | last1 = Slonim | first1 = Donna
 | last2 = Kruglyak | first2 = Leonid
 | last3 = Stein | first3 = Lincoln
 | last4 = Lander | first4 = Eric | author4-link = Eric Lander
 | doi = 10.1089/cmb.1997.4.487
 | issue = 4
 | journal = [[Journal of Computational Biology]]
 | pages = 487–504
 | title = Building human genome maps with radiation hybrids
 | volume = 4
 | year = 1997| pmid = 9385541
 }}.</ref> and was shown to be [[NP-complete]] by {{harvtxt|Opatrný|1979}}.<ref name="o79"/>