×

On algebraic expressions of directed grid graphs. (English) Zbl 1377.05173

Arumugam, S. (ed.) et al., Proceedings of the 9th international workshop on graph labelings (IWOGL 2016), Cracow, Poland, July 7–9, 2016. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 60, 39-46 (2017).
Summary: The paper investigates relationship between algebraic expressions and labeled graphs. We consider directed grid graphs having \(m\) rows and \(n\) columns. Our intent is to simplify the expressions of these graphs. With that end in view, we describe two algorithms which generate expressions of polynomial sizes for directed grid graphs.
For the entire collection see [Zbl 1375.05003].

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C20 Directed graphs (digraphs), tournaments
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)

Software:

JBool
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bein, W. W.; Kamburowski, J.; Stallmann, M. F.M., Optimal Reduction of Two-Terminal Directed Acyclic Graphs, SIAM Journal of Computing, 21, 6, 1112-1129 (1992) · Zbl 0768.68119
[2] Duffin, R. J., Topology of Series-Parallel Networks, Journal of Mathematical Analysis and Applications, 10, 303-318 (1965) · Zbl 0128.37002
[3] Finta, L.; Liu, Z.; Milis, I.; Bampis, E., Scheduling UET-UCT Series-Parallel Graphs on Two Processors, Theoretical Computer Science, 162, 2, 323-340 (1996) · Zbl 0877.68008
[4] Golumbic, M. Ch.; Gurvich, V., Read-Once Functions, (Crama, Y.; Hammer, P. S., Boolean Functions: Theory, Algorithms and Applications (2011), Cambridge University Press)
[5] Golumbic, M. Ch.; Perl, Y., Generalized Fibonacci Maximum Path Graphs, Discrete Mathematics, 28, 237-245 (1979) · Zbl 0427.05044
[6] Korenblit, M., A Note on Algebraic Expressions of Rhomboidal Labeled Graphs, Electronic Notes in Discrete Mathematics, 48, 243-250 (2015) · Zbl 1347.05198
[7] Korenblit, M.; Levit, V. E., On Algebraic Expressions of Series-Parallel and Fibonacci Graphs, (Discrete Mathematics and Theoretical Computer Science, Proc. 4th Int. Conf., DMTCS 2003. Discrete Mathematics and Theoretical Computer Science, Proc. 4th Int. Conf., DMTCS 2003, LNCS, vol. 2731 (2003), Springer), 215-224 · Zbl 1038.68086
[8] Korenblit, M.; Levit, V. E., A One-Vertex Decomposition Algorithm for Generating Algebraic Expressions of Square Rhomboids, (Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, Proc. Third Joint Int. Conf., FAW-AAIM 2013. Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, Proc. Third Joint Int. Conf., FAW-AAIM 2013, LNCS, vol. 7924 (2013), Springer), 94-105 · Zbl 1303.05197
[9] Oikawa, M. K.; Ferreira, J. E.; Malkowski, S.; Pu, C., Towards Algorithmic Generation of Business Processes: From Business Step Dependencies to Process Algebra Expressions, (Business Process Management, Proc. 7th Int. Conf., BPM 2009. Business Process Management, Proc. 7th Int. Conf., BPM 2009, LNCS, vol. 5701 (2009), Springer), 80-96
[10] Satyanarayana, A.; Wood, R. K., A Linear Time Algorithm for Computing K-Terminal Reliability in Series-Parallel Networks, SIAM Journal of Computing, 14, 4, 818-832 (1985) · Zbl 0575.68072
[11] Tamir, A., A Strongly Polynomial Algorithm for Minimum Convex Separable Quadratic Cost Flow Problems on Two-Terminal Series-Parallel Networks, Mathematical Programming, 59, 117-132 (1993) · Zbl 0795.90021
[12] 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.