A \(\min\)-\(\max\) relation in flowgraphs and some applications
From MaRDI portal
Publication:1752483
DOI10.1016/j.dam.2017.04.038zbMath1387.05103OpenAlexW2618776424MaRDI QIDQ1752483
Carlos E. Ferreira, Álvaro J. P. Franco
Publication date: 24 May 2018
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2017.04.038
junctionnearest common ancestordominator treeflowgraph\(\min\)-\(\max\) relationvertex-disjoint dipath
Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Directed graphs (digraphs), tournaments (05C20)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A min-max relation in flowgraphs
- All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time
- New algorithms for the LCA problem and the binary tree reconstruction problem
- Finding level-ancestors in trees
- Finding lowest common ancestors in arbitrarily directed trees
- Faster algorithms for finding lowest common ancestors in directed acyclic graphs
- An efficient algorithm for finding maximum cycle packings in reducible flow graphs
- Applications of Path Compression on Balanced Trees
- A Minimax Arc Theorem for Reducible Flow Graphs
- Fast Algorithms for Finding Nearest Common Ancestors
- Fast Lowest Common Ancestor Computations in Dags
- All-Pairs Ancestor Problems in Weighted Dags
- Finding a minimum feedback arc set in reducible flow graphs
- A fast algorithm for finding dominators in a flowgraph
- Characterizations of Reducible Flow Graphs
- On Finding Lowest Common Ancestors in Trees
- Algorithms for Junctions in Acyclic Digraphs
- Dynamic LCA Queries on Trees
- Multiplying matrices faster than coppersmith-winograd
- Lowest common ancestors in trees and directed acyclic graphs
This page was built for publication: A \(\min\)-\(\max\) relation in flowgraphs and some applications
