Top

Published in:

2020 | OriginalPaper | Chapter

On Algebraic Expressions of Two-Terminal Directed Acyclic Graphs

Authors : Mark Korenblit, Vadim E. Levit

Published in: Algorithms and Discrete Applied Mathematics

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The paper investigates relationship between algebraic expressions and graphs. Our intent is to simplify graph expressions and eventually find their shortest representations. We describe the decomposition method for generating expressions of complete st-dags (two-terminal directed acyclic graphs) and estimate the corresponding expression complexities. Using these findings, we present an \(2^{O\left( \log ^{2}n\right) }\) upper bound of a length of the shortest expression for every st-dag of order n.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter List Distinguishing Number of Power of Hypercube and Cartesian Powers of a Graph

next chapter The Relative Oriented Clique Number of Triangle-Free Planar Graphs Is 10

Anderson, D.F., Levy, R., Shapiro, J.: Zero-divisor graphs, von Neumann regular rings, and Boolean algebras. J. Pure Appl. Algebra 180, 221–241 (2003)MathSciNetMATHCrossRef

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)MathSciNetMATHCrossRef

Duffin, R.J.: Topology of series-parallel networks. J. Math. Anal. Appl. 10, 303–318 (1965)MathSciNetMATHCrossRef

Fernau, H.: Algorithms for learning regular expressions from positive data. Inf. Comput. 207, 521–541 (2009)MathSciNetMATHCrossRef

Fernau, H., Ryan, J.F., Sugeng, K.A.: A sum labelling for the generalised friendship graph. Discrete Math. 308, 734–740 (2008)MathSciNetMATHCrossRef

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)MathSciNetMATHCrossRef

Golumbic, M.C., Gurvich, V.: Read-once functions. In: Crama, Y., Hammer, P.L. (eds.) Boolean Functions: Theory, Algorithms and Applications, pp. 519–560. Cambridge University Press, New York (2011)

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)MathSciNetMATHCrossRef

Golumbic, M.C., Perl, Y.: Generalized Fibonacci maximum path graphs. Discrete Math. 28, 237–245 (1979)MathSciNetMATHCrossRef

10.

Gulan, S.: Series parallel digraphs with loops. Graphs encoded by regular expression. Theory Comput. Syst. 53, 126–158 (2013)MathSciNetMATHCrossRef

11.

Korenblit, M.: Efficient computations on networks. Ph.D. Thesis, Bar-Ilan University, Israel (2004)

12.

Korenblit, M.: Decomposition methods for generating algebraic expressions of full square rhomboids and other graphs. Discrete Appl. Math. 228, 60–72 (2017)MathSciNetMATHCrossRef

13.

Korenblit, M., Levit, V.E.: On algebraic expressions of series-parallel and Fibonacci graphs. In: Calude, C.S., Dinneen, M.J., Vajnovszki, V. (eds.) DMTCS 2003. LNCS, vol. 2731, pp. 215–224. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-45066-1_17MATHCrossRef

14.

Korenblit, M., Levit, V.E.: Estimation of expressions’ complexities for two-terminal directed acyclic graphs. Electron. Not. Discrete Math. 63, 109–116 (2017)MathSciNetMATHCrossRef

15.

Mintz, A., Golumbic, M.C.: Factoring Boolean functions using graph partitioning. Discrete Appl. Math. 149(1–3), 131–153 (2005)MathSciNetMATHCrossRef

16.

Mundici, D.: Functions computed by monotone boolean formulas with no repeated variables. Theoret. Comput. Sci. 66, 113–114 (1989)MathSciNetMATHCrossRef

17.

Mundici, D.: Solution of Rota’s problem on the order of series-parallel networks. Adv. Appl. Math. 12, 455–463 (1991)MathSciNetMATHCrossRef

18.

Naumann, V.: Measuring the distance to series-parallelity by path expressions. In: Mayr, E.W., Schmidt, G., Tinhofer, G. (eds.) WG 1994. LNCS, vol. 903, pp. 269–281. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-59071-4_54CrossRef

19.

Oikawa, M.K., Ferreira, J.E., Malkowski, S., Pu, C.: Towards algorithmic generation of business processes: from business step dependencies to process algebra expressions. In: Dayal, U., Eder, J., Koehler, J., Reijers, H.A. (eds.) BPM 2009. LNCS, vol. 5701, pp. 80–96. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03848-8_7CrossRef

20.

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)MathSciNetMATHCrossRef

21.

Savicky, P., Woods, A.R.: The number of boolean functions computed by formulas of a given size. Random Struct. Algorithms 13, 349–382 (1998)MathSciNetMATHCrossRef

22.

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)MathSciNetMATHCrossRef

23.

Wang, A.R.R.: Algorithms for multilevel logic optimization. Ph.D. Thesis, University of California, Berkeley (1989)

Title: On Algebraic Expressions of Two-Terminal Directed Acyclic Graphs
Authors: Mark Korenblit
Vadim E. Levit
Publisher: Springer International Publishing
Book: Algorithms and Discrete Applied Mathematics
Print ISBN: 978-3-030-39218-5

Electronic ISBN: 978-3-030-39219-2

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-39219-2_21

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner