Maximum likelihood analysis of the Ford-Fulkerson method on special graphs

DOI10.1007/S00453-015-9998-5zbMath1339.68342OpenAlexW2101318995MaRDI QIDQ289909

Ulrich Laube, Markus E. Nebel

Publication date: 31 May 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-015-9998-5

zbMATH Keywords

generating functionsanalysis of algorithmsgrid graphsrandom geometric graphsaverage caseFord-Fulkerson maxflowmaximum likelihood analysisstochastic context free grammars

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Random graphs (graph-theoretic aspects) (05C80) Grammars and rewriting systems (68Q42) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Uses Software

• MaLiJAn

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum likelihood analysis of algorithms and data structures
• R. A. Fisher and the making of maximum likelihood 1912--1922
• Beyond the flow decomposition barrier
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Average-case analysis of algorithms for matchings and related problems
• Random Geometric Graphs
• Order Statistics
• A Computational Study of the Pseudoflow and Push-Relabel Algorithms for the Maximum Flow Problem
• Max flows in O(nm) time, or better
• Random Graphs

This page was built for publication: Maximum likelihood analysis of the Ford-Fulkerson method on special graphs