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

DOI10.1007/S00453-015-9998-5MaRDI QIDQ289909zbMATH OpenOpenAlexFDO

Authors 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

analysis of algorithmsgenerating functionsrandom geometric graphsaverage caseFord-Fulkerson maxflowgrid graphsmaximum likelihood analysisstochastic context free grammars

Mathematics Subject Classification ID

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

Recommendations

• A Randomized Maximum-Flow Algorithm
• An $o(n^3 )$-Time Maximum-Flow Algorithm
• Probabilistic Analysis of Network Flow Algorithms
• scientific article; zbMATH DE number 177817
• A new approach to the maximum-flow problem

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• scientific article; zbMATH DE number 3238653 (Why is no real title available?)
• scientific article; zbMATH DE number 3308993 (Why is no real title available?)
• scientific article; zbMATH DE number 3349645 (Why is no real title available?)
• A computational study of the pseudoflow and push-relabel algorithms for the maximum flow problem
• Analytic combinatorics
• Average-case analysis of algorithms for matchings and related problems
• Beyond the flow decomposition barrier
• Max flows in \(O(nm)\) time, or better
• Maximum likelihood analysis of algorithms and data structures
• Order Statistics
• R. A. Fisher and the making of maximum likelihood 1912--1922
• Random Geometric Graphs
• Random Graphs
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Describes a project that uses

Uses Software

• MaLiJAn

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q289909)