×

Estimation of expressions’ complexities for two-terminal directed acyclic graphs. (English) Zbl 1383.05133

Sinha, Deepa (ed.) et al., International conference on current trends in graph theory and computation, CTGTC-2016, New Delhi, India, September 17–19, 2016. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 63, 109-116 (2017).
Summary: The paper investigates relationship between algebraic expressions and graphs. Our intention is to simplify graph expressions and eventually find their shortest representations. We prove the decomposition lemma which asserts that the shortest expression of a subgraph of a graph \(G\) is not larger than the shortest expression of \(G\). Using this finding, we estimate an upper bound of a size of the shortest expression for any two-terminal directed acyclic graph.
For the entire collection see [Zbl 1384.05002].

MSC:

05C20 Directed graphs (digraphs), tournaments
05C78 Graph labelling (graceful graphs, bandwidth, 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 J. Comput., 21, 6, 1112-1129 (1992) · Zbl 0768.68119
[2] Duffin, R. J., Topology of Series-Parallel Networks, J. Math. Anal. Appl., 10, 303-318 (1965) · Zbl 0128.37002
[3] Golumbic, M. Ch.; Gurvich, V., Read-Once Functions, (Crama, Y.; Hammer, P. S., Boolean Functions: Theory, Algorithms and Applications (2011), Cambridge University Press)
[4] 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
[5] Golumbic, M. Ch.; Perl, Y., Generalized Fibonacci Maximum Path Graphs, Discrete Math., 28, 237-245 (1979) · Zbl 0427.05044
[6] Korenblit, M., Efficient Computations on Networks (2004), Bar-Ilan University: Bar-Ilan University Israel, Ph.D. thesis
[7] Korenblit, M., Decomposition methods for generating algebraic expressions of full square rhomboids and other graphs, Discrete Appl. Math. (2016), (available online) · Zbl 1365.05112
[8] 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
[9] Mintz, A.; Golumbic, M. C., Factoring Boolean Functions Using Graph Partitioning, Discrete Appl. Math., 149, 1-3, 131-153 (2005) · Zbl 1101.94033
[10] Naumann, V., Measuring the Distance to Series-Parallelity by Path Expressions, (Graph-Theoretic Concepts in Computer Science, Proc. 20th Int. Workshop, WG ’94. Graph-Theoretic Concepts in Computer Science, Proc. 20th Int. Workshop, WG ’94, LNCS, vol. 903 (1994), Springer), 269-281
[11] 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.