On lengths of edge-labeled graph expressions
DOI10.1016/j.dam.2022.04.015zbMath1494.05096OpenAlexW4281559424MaRDI QIDQ2161278
Vadim E. Levit, Mark Korenblit
Publication date: 4 August 2022
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2022.04.015
complexitydecompositionseries-parallel graphtwo-terminal directed acyclic graphedge-labeled graphalgebraic expression
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Directed graphs (digraphs), tournaments (05C20)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Series parallel digraphs with loops
- Algorithms for learning regular expressions from positive data
- Functions computed by monotone Boolean formulas with no repeated variables
- Generalized Fibonacci maximum path graphs
- Solution of Rota's problem on the order of series-parallel networks
- Scheduling UET-UCT series-parallel graphs on two processors
- Zero-divisor graphs, von Neumann regular rings, and Boolean algebras.
- Decomposition methods for generating algebraic expressions of full square rhomboids and other graphs
- A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks
- Factoring Boolean functions using graph partitioning
- Topology of series-parallel networks
- Estimation of expressions' complexities for two-terminal directed acyclic graphs
- A sum labelling for the generalised friendship graph
- Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees
- A Linear-Time Algorithm for Computing K-Terminal Reliability in Series-Parallel Networks
- Optimal Reduction of Two-Terminal Directed Acyclic Graphs
- The number of Boolean functions computed by formulas of a given size
This page was built for publication: On lengths of edge-labeled graph expressions
