×

zbMATH — the first resource for mathematics

An efficient PQ-graph algorithm for solving the graph-realization problem. (English) Zbl 0438.68028

MSC:
68R10 Graph theory (including graph drawing) in computer science
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, Mass · Zbl 0286.68029
[2] \scR. E. Bixby and W. H. Cunningham, Converting linear programs to network problems, Math. Operations Res., in press. · Zbl 0442.90095
[3] Booth, K.S.; Lueker, G.S., Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. comput. system sci., 13, 335-379, (1976) · Zbl 0367.68034
[4] Fujishige, S., An efficient algorithm for solving the graph-realization problem by means of PQ-trees, (), 1012-1015
[5] Gould, R., Graphs and vector spaces, J. math. phys., 37, 193-214, (1958) · Zbl 0084.39601
[6] Iri, M.; Iri, M., On the synthesis of loop and cutset matrices and the related problems, RAAG res. notes, ser. 3, RAAG mem. A, 5, No. 50, 4-38, (1968) · Zbl 0219.73107
[7] Iri, M., Network flow, transportation and scheduling: theory and algorithm, (1969), Academic Press New York · Zbl 0281.90032
[8] Mayeda, W., Graph theory, (1972), Wiley New York · Zbl 0111.32104
[9] Seshu, S.; Reed, M.B., Linear graphs and electrical networks, (1961), Addison-Wesley Reading, Mass · Zbl 0102.34001
[10] Tarjan, R.E., Efficiency of a good but not linear set union algorithm, J. assoc. comput. Mach., 22, 215-225, (1975) · Zbl 0307.68029
[11] Tomizawa, N., An O(m3) algorithm for solving the realization problem of graphs—on combinatorial characterizations of graphic (0, 1)-matrices, (), [In Japanese]
[12] Tutte, W.T., An algorithm for determining whether a given binary matroid is graphic, (), 905-917 · Zbl 0097.38905
[13] Tutte, W.T., From matrices to graphs, Canad. J. math., 16, 108-128, (1964) · Zbl 0138.19202
[14] Tutte, W.T., Connectivity in graphs, (1966), Univ. of Toronto Press London · Zbl 0146.45603
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.