A \(\min\)-\(\max\) relation in flowgraphs and some applications

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

zbMATH Keywords

junctionnearest common ancestordominator treeflowgraph\(\min\)-\(\max\) relationvertex-disjoint dipath

Mathematics Subject Classification ID

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