{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:12:49Z","timestamp":1760242369761,"version":"build-2065373602"},"reference-count":19,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2017,6,27]],"date-time":"2017-06-27T00:00:00Z","timestamp":1498521600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The discrepancy BR for an m \u00d7 n 0, 1-matrix from Brualdi and Sanderson in 1998 is defined as the minimum number of 1 s that need to be shifted in each row to the left to achieve its Ferrers matrix, i.e., each row consists of consecutive 1 s followed by consecutive 0 s. For ecological bipartite networks, BR describes a nested set of relationships. Since two different labelled networks can be isomorphic, but possess different discrepancies due to different adjacency matrices, we define a metric determining the minimum discrepancy in an isomorphic class. We give a reduction to k \u2264 n minimum weighted perfect matching problems. We show on 289 ecological matrices (given as a benchmark by Atmar and Patterson in 1995) that classical discrepancy can underestimate the nestedness by up to 30%.<\/jats:p>","DOI":"10.3390\/a10030074","type":"journal-article","created":{"date-parts":[[2017,6,28]],"date-time":"2017-06-28T10:25:56Z","timestamp":1498645556000},"page":"74","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Isomorphic Version of Brualdi\u2019s and Sanderson\u2019s Nestedness"],"prefix":"10.3390","volume":"10","author":[{"given":"Annabell","family":"Berger","sequence":"first","affiliation":[{"name":"Department of Computer Science, Martin-Luther University, 06120 Halle-Wittenberg, Germany"}]},{"given":"Berit","family":"Schreck","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Martin-Luther University, 06120 Halle-Wittenberg, Germany"}]}],"member":"1968","published-online":{"date-parts":[[2017,6,27]]},"reference":[{"key":"ref_1","unstructured":"Hult\u00e9n, E. (1937). Outline of the History of Arctic and Boreal Biota During the Quaternary Periods, AICS Research, Inc."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1111\/j.1600-0706.2008.17053.x","article-title":"A consumer\u2019s guide to nestedness analysis","volume":"118","author":"Ulrich","year":"2009","journal-title":"Oikos"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"9383","DOI":"10.1073\/pnas.1633576100","article-title":"The nested assembly of plant-animal mutualistic networks","volume":"100","author":"Bascompte","year":"2003","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1111\/j.1461-0248.2007.01137.x","article-title":"Network structural properties mediate the stability of mutualistic communities","volume":"11","author":"Okuyama","year":"2008","journal-title":"Ecol. Lett."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1018","DOI":"10.1038\/nature07950","article-title":"The architecture of mutualistic networks minimizes competition and increases biodiversity","volume":"458","author":"Bastolla","year":"2009","journal-title":"Nature"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"853","DOI":"10.1126\/science.1188321","article-title":"Stability of Ecological Communities and the Architecture of Mutualistic and Trophic Networks","volume":"329","author":"Fontaine","year":"2010","journal-title":"Science"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"251","DOI":"10.2307\/2369545","article-title":"A Constructive Theory of Partitions, Arranged in Three Acts, an Interact and an Exodion","volume":"5","author":"Sylvester","year":"1882","journal-title":"Am. J. Math."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Gessel, I., and Rota, G.C. (1987). Combinatorial Properties of Matrices of Zeros and Ones. Classic Papers in Combinatorics, Birkh\u00e4user Boston.","DOI":"10.1007\/978-0-8176-4842-8"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Brualdi, R.A. (2006). Combinatorial Matrix Classes, Cambridge University Press.","DOI":"10.1017\/CBO9780511721182"},{"key":"ref_10","unstructured":"Mahadev, N.V.R., and Peled, U.N. (1995). Threshold Graphs and Related Topics, North-Holland."},{"key":"ref_11","first-page":"1","article-title":"Discrepancy of matrices of zeros ond ones","volume":"6","author":"Brualdi","year":"1999","journal-title":"Electron. J. Comb."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L., and Plummer, M.D. (2009). Matching Theory, AMS Chelsea Publishing.","DOI":"10.1090\/chel\/367"},{"key":"ref_13","unstructured":"Gabow, H. (1974). Implementation of Algorithms for Maximum Matching on Nonbipartite Graph. [Ph.D. Thesis, Stanford University]."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1137\/0602010","article-title":"Computing the Minimum Fill-In is NP-Complete","volume":"2","author":"Yannakakis","year":"1981","journal-title":"SIAM J. Algebraic Discret. Methods"},{"key":"ref_15","unstructured":"Garey, M.R., and Johnson, D.S. (1990). Computers and Intractability; A Guide to the Theory of NP-Completeness, W. H. Freeman & Co."},{"key":"ref_16","unstructured":"Junttila, E. (2011). Patterns in permuted binary matrices. [Ph.D. Thesis, University of Helsinki]."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1007\/s004420050784","article-title":"Nested species subsets, gaps, and discrepancy","volume":"119","author":"Brualdi","year":"1998","journal-title":"Oecologia"},{"key":"ref_18","unstructured":"Atmar, W., and Patterson, B.D. (1995). The Nestedness Temperature Calculator: A Visual Basic Program, Including 294 Presence-Absence Matrices, AICS Research, Inc."},{"key":"ref_19","unstructured":"(2017, June 23). Nested. Available online: https:\/\/www.dropbox.com\/sh\/jbi3bgsalw6e6kt\/AAAyDRth-1knfjhYwRqAgqEya?dl=0."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/10\/3\/74\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:40:32Z","timestamp":1760208032000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/10\/3\/74"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,27]]},"references-count":19,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2017,9]]}},"alternative-id":["a10030074"],"URL":"https:\/\/doi.org\/10.3390\/a10030074","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2017,6,27]]}}}