TY - JOUR
T1 - Estimation of Expressions’ Complexities for Two-Terminal Directed Acyclic Graphs
AU - Korenblit, Mark
AU - Levit, Vadim E.
N1 - Publisher Copyright:
© 2017 Elsevier B.V.
PY - 2017/12
Y1 - 2017/12
N2 - 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.
AB - 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.
KW - Two-terminal directed acyclic graph
KW - algebraic expression
KW - complexity
KW - edge-labeled graph
KW - series-parallel graph
UR - http://www.scopus.com/inward/record.url?scp=85036548520&partnerID=8YFLogxK
U2 - 10.1016/j.endm.2017.11.005
DO - 10.1016/j.endm.2017.11.005
M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???
AN - SCOPUS:85036548520
SN - 1571-0653
VL - 63
SP - 109
EP - 116
JO - Electronic Notes in Discrete Mathematics
JF - Electronic Notes in Discrete Mathematics
ER -