TY - JOUR
T1 - On lengths of edge-labeled graph expressions
AU - Korenblit, Mark
AU - Levit, Vadim E.
N1 - Publisher Copyright:
© 2022 Elsevier B.V.
PY - 2022/10/15
Y1 - 2022/10/15
N2 - This paper investigates relationship between algebraic expressions and graphs. Our intent is to simplify graph expressions and eventually find their shortest representations. We prove the monotonicity results allowing to assert that the length of a shortest expression of any subgraph of a given graph is not greater than the length of a shortest expression of the graph. 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 2Olog2n upper bound for the length of a shortest expression for every n-vertex st-dag.
AB - This paper investigates relationship between algebraic expressions and graphs. Our intent is to simplify graph expressions and eventually find their shortest representations. We prove the monotonicity results allowing to assert that the length of a shortest expression of any subgraph of a given graph is not greater than the length of a shortest expression of the graph. 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 2Olog2n upper bound for the length of a shortest expression for every n-vertex st-dag.
KW - Algebraic expression
KW - Complexity
KW - Decomposition
KW - Edge-labeled graph
KW - Series–parallel graph
KW - Two-terminal directed acyclic graph
UR - http://www.scopus.com/inward/record.url?scp=85130775619&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2022.04.015
DO - 10.1016/j.dam.2022.04.015
M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???
AN - SCOPUS:85130775619
SN - 0166-218X
VL - 319
SP - 583
EP - 594
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -