Korenblit, M. Decomposition methods for generating algebraic expressions of full square rhomboids and other graphs. (English) Zbl 1365.05112 Discrete Appl. Math. 228, 60-72 (2017). Summary: The paper investigates relationship between algebraic expressions and two-terminal directed acyclic graphs. We consider rhomboidal non-series-parallel graphs, specifically, a digraph called a full square rhomboid. Our intention is to simplify the expressions of full square rhomboids. We describe two decomposition methods for generating expressions of rhomboidal graphs and carry out their comparative analysis. Cited in 2 Documents MSC: 05C20 Directed graphs (digraphs), tournaments Keywords:two-terminal directed acyclic graph; series-parallel graph; rhomboid; algebraic expression; decomposition Software:JBool PDFBibTeX XMLCite \textit{M. Korenblit}, Discrete Appl. Math. 228, 60--72 (2017; Zbl 1365.05112) Full Text: DOI References: [1] Barabási, A.-L.; Albert, R., Emergence of scaling in random networks, Science, 286, 5439, 509-512 (1999) · Zbl 1226.05223 [2] Bein, W. W.; Kamburowski, J.; Stallmann, M. F.M., Optimal reduction of two-terminal directed acyclic graphs, SIAM J. Comput., 21, 6, 1112-1129 (1992) · Zbl 0768.68119 [3] Chrobak, M.; Eppstein, D., Planar orientations with low out-degree and compaction of adjacency matrices, Theoret. Comput. Sci., 86, 2, 243-266 (1991) · Zbl 0735.68015 [4] Cormen, T. H.; Leiseron, C. E.; Rivest, R. L., Introduction to Algorithms (2001), The MIT Press: The MIT Press Cambridge, Massachusetts [5] Duffin, R. J., Topology of series-parallel networks, J. Math. Anal. Appl., 10, 303-318 (1965) · Zbl 0128.37002 [6] Finta, L.; Liu, Z.; Milis, I.; Bampis, E., Scheduling UET-UCT series-parallel graphs on two processors, Theoret. Comput. Sci., 162, 2, 323-340 (1996) · Zbl 0877.68008 [7] Golumbic, M. C.; Gurvich, V., Read-once functions, (Crama, Y.; Hammer, P. L., Boolean Functions: Theory, Algorithms and Applications (2011), Cambridge University Press: Cambridge University Press New York), 519-560 [8] Golumbic, M. C.; Mintz, A.; Rotics, U., Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial k-trees, Discrete Appl. Math., 154, 10, 1465-1477 (2006) · Zbl 1131.68072 [9] Golumbic, M. C.; Perl, Y., Generalized fibonacci maximum path graphs, Discrete Math., 28, 237-245 (1979) · Zbl 0427.05044 [10] Irani, S., Coloring inductive graphs on-line, Algorithmica, 11, 1, 53-72 (1994) · Zbl 0784.68067 [11] Korenblit, M.; Levit, V. E., On algebraic expressions of series-parallel and fibonacci graphs, (Calude, C. S.; Dinneen, M. J.; Vajnovzki, V., DMTCS 2003. DMTCS 2003, LNCS, vol. 2731 (2003), Springer: Springer Heidelberg), 215-224 · Zbl 1038.68086 [13] Korenblit, M.; Levit, V. E., A one-vertex decomposition algorithm for generating algebraic expressions of square rhomboids, (Fellows, M.; Tan, X.; Zhu, B., FAW-AAIM 2013. FAW-AAIM 2013, LNCS, vol. 7924 (2013), Springer: Springer Heidelberg), 94-105 · Zbl 1303.05197 [16] Mintz, A.; Golumbic, M. C., Factoring boolean functions using graph partitioning, Discrete Appl. Math., 149, 1-3, 131-153 (2005) · Zbl 1101.94033 [17] Mundici, D., Functions computed by monotone boolean formulas with no repeated variables, Theoret. Comput. Sci., 66, 113-114 (1989) · Zbl 0674.94025 [18] Mundici, D., Solution of rota’s problem on the order of series-parallel networks, Adv. Appl. Math., 12, 455-463 (1991) · Zbl 0748.94024 [19] Noy, M.; Ribó, A., Recursively constructible families of graphs, Adv. Appl. Math., 32, 350-363 (2004) · Zbl 1041.05050 [20] Oikawa, M. K.; Ferreira, J. E.; Malkowski, S.; Pu, C., (Dayal, U.; Eder, J.; Koehler, J.; Reijers, H. A., BPM 2009. BPM 2009, LNCS, vol. 5701 (2009), Springer: Springer Heidelberg), 80-96 [21] (Rosen, K. H., Handbook of Discrete and Combinatorial Mathematics (2000), CRC Press: CRC Press Boca Raton) · Zbl 1044.00002 [22] Satyanarayana, A.; Wood, R. K., A linear time algorithm for computing k-terminal reliability in series-parallel networks, SIAM J. Comput., 14, 4, 818-832 (1985) · Zbl 0575.68072 [23] Savicky, P.; Woods, A. R., The number of boolean functions computed by formulas of a given size, Random Structures Algorithm, 13, 349-382 (1998) · Zbl 0959.68525 [24] Tamir, A., A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks, Math. Program., 59, 117-132 (1993) · Zbl 0795.90021 [25] Wang, A. R.R., Algorithms for multilevel logic optimization (1989), University of California: University of California Berkeley, (Ph.D. thesis) 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.