×
Truemper, K.

On the efficiency of representability tests for matroids. (English) Zbl 0505.05021

Eur. J. Comb. 3, 275-291 (1982).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0505.05021

Cited in 11 Documents

MSC:

05B35 Combinatorial aspects of matroids and geometric lattices
68Q25 Analysis of algorithms and problem complexity

Keywords:

matroid representation; binary matroid; graphic matroid; polynomial time algorithms
Cite Review PDF
Full Text: DOI

References:

[1] Bixby, R. E.; Cunningham, W. H., Converting linear programs to network problems, Math. Oper. Res., 5, 321-357 (1980) · Zbl 0442.90095
[2] Cunningham, W. H., A combinatorial decomposition theory, Dissertation (1973), University of Waterloo · Zbl 0385.05022
[3] Fujishige, S., An efficient PQ-graph algorithm for solving the graph realization problem, J. Comput. System Sci., 21, 63-86 (1980) · Zbl 0438.68028
[4] Inukai, T.; Weinberg, L., Graph-realizability of matroids, Ann. N. Y. Acad. Sci., 319, 289-305 (1979) · Zbl 0478.05029
[5] Iri, M., On the synthesis of loop and cutset matrices and the related problems, RAAG Memoirs, 4, 376-410 (1968)
[6] Krogdahl, S., The dependence graph for bases in a matroid, Discrete Math., 19, 47-59 (1977) · Zbl 0366.05024
[7] Møller Jensen, P.; Korte, B., Complexity of matroid property algorithms, Report No. 78124-OR (1979), Institut für Ökonometric and Operations Research, University of Bonn
[8] Robinson, G. C.; Welsh, D. J. A., The computational complexity of matroid properties, Math. Proc. Cambridge Philos. Soc., 87, 29-45 (1980) · Zbl 0434.68030
[9] Seymour, P. D., Decomposition of regular matroids, J. Combin. Theory Ser. B, 28, 305-359 (1980) · Zbl 0443.05027
[10] P. D. Seymour, Recognizing graphic matroids, Combinatorica (to appear).; P. D. Seymour, Recognizing graphic matroids, Combinatorica (to appear). · Zbl 0501.05022
[11] Seymour, P. D.; Walton, P. N., Detecting matroid minors, J. London Math. Soc., 23, 2, 193-203 (1981) · Zbl 0487.05016
[12] Truemper, K., Alpha-balanced graphs and matrices and GF(3)-representability of matroids, J. Combin. Theory Ser. B, 32, 112-139 (1982) · Zbl 0478.05026
[13] Truemper, K., Complexity of representability tests for matroids, Working Paper (1979), University of Texas: University of Texas Dallas · Zbl 0505.05021
[14] Truemper, K., An efficient test for regularity of matroids, Working Paper (1980), University of Texas: University of Texas Dallas · Zbl 0397.05043
[15] Tutte, W. T., An algorithm for determining whether a given binary matroid is graphic, Proc. Amer. Math. Soc., 11, 905-917 (1960) · Zbl 0097.38905
[16] Tutte, W. T., Lectures on matroids, J Res. Nat. Bur. Standards Sect. B, 69, 1-47 (1965) · Zbl 0151.33801
[17] Tutte, W. T., Introduction to the Theory of Matroids (1971), American Elsevier: American Elsevier New York · Zbl 0231.05027
[18] Welsh, D. J.A., Matroid Theory (1976), Academic Press: Academic Press London · Zbl 0343.05002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.