Recognizing Series-Parallel Matrices in Linear Time

References

• Berge C (1972) Balanced matrices. Math. Programming 2(1):19–31.Crossref, Google Scholar
• Bixby RE, Wagner DK (1988) An almost linear-time algorithm for graph realization. Math. Oper. Res. 13(1):99–123.Link, Google Scholar
• Brandstädt A, Le VB, Spinrad JP (1999) Graph Classes: A Survey (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• Chaourar B, Oxley J (2003) On series-parallel extensions of uniform matroids. Eur. J. Combin. 24(7):877–879.Crossref, Google Scholar
• Chen W, Dawande M, Janakiraman G (2014) Integrality in Stochastic Inventory Models. Production Oper. Management 23(9):1646–1663.Crossref, Google Scholar
• Conforti M, Fiorini S, Huynh T, Weltge S (2022) Extended formulations for stable set polytopes of graphs without two disjoint odd cycles. Math. Programming 192(1):547–566.Crossref, Google Scholar
• Dean MD, Gurumurthy KM, de Souza F, Auld J, Kockelman KM (2022) Synergies between repositioning and charging strategies for shared autonomous electric vehicle fleets. Transportation Res. Part D Transport Environment 108:103314.Crossref, Google Scholar
• Deuker P, Friedrich U (2023) Recognizing integrality of weighted rectangles partitions. https://optimization-online.org/?p=18353.Google Scholar
• Duffin RJ (1965) Topology of series-parallel networks. J. Math. Anal. Appl. 10(2):303–318.Crossref, Google Scholar
• Fujishige S (1980) An efficient PQ-graph algorithm for solving the graph-realization problem. J. Comput. System Sci. 21(1):63–86.Crossref, Google Scholar
• Gleixner A, Hendel G, Gamrath G, Achterberg T, Bastubbe M, Berthold T, Christophel PM, et al. (2021) MIPLIB 2017: Data-driven compilation of the 6th mixed-integer programming library. Math. Programming Comput. 13:443–490.Crossref, Google Scholar
• Henselman G, Dłotko P (2014) Combinatorial invariants of multidimensional topological network data. 2014 IEEE Global Conf. Signal Inform. Processing (IEEE, Piscataway, NJ), 828–832.Google Scholar
• Hoffman AJ, Kruskal JB (1956) Integral boundary points of convex polyhedra. Linear Inequalities and Related Systems, vol. 38 (Princeton University Press, Princeton, NJ), 223–246.Google Scholar
• Lehman A (1979) On the width-length inequality. Math. Programming 16(1):245–259.Crossref, Google Scholar
• Oxley JG (1992) Matroid Theory, vol. 1997 (Oxford University Press, Oxford, UK).Google Scholar
• Padberg MW (1984) A characterization of perfect matrices. Topics on Perfect Graphs, North-Holland Mathematics Studies, vol. 88 (North-Holland, Amsterdam), 169–178.Crossref, Google Scholar
• Schrijver A (1986) Theory of Linear and Integer Programming (John Wiley & Sons, Inc., New York).Google Scholar
• Tarjan RE (1975) Efficiency of a good but not linear set union algorithm. J. ACM 22(2):215–225.Crossref, Google Scholar
• Truemper K (1990) A decomposition theory for matroids. V. Testing of matrix total unimodularity. J. Combin. Theory Ser. B 49(2):241–281.Crossref, Google Scholar
• Truemper K (1998) Matroid Decomposition, revised ed. (Academic Press, Cambridge, MA).Google Scholar
• Tutte WT (1958) A homotopy theorem for matroids, II. Trans. Amer. Math. Soc. 88(1):161–174.Google Scholar
• Valdes J, Tarjan RE, Lawler EL (1982) The recognition of series parallel digraphs. SIAM J. Comput. 11(2):298–313.Crossref, Google Scholar
• Walter M, Truemper K (2013) Implementation of a unimodularity test. Math. Programming Comput. 5(1):57–73.Crossref, Google Scholar
• Walter M, Truemper K (2023) CMR—Combinatorial matrix recognition library. Documentation: https://discopt.github.io/cmr, source code: https://github.com/discopt/cmr.Google Scholar