An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths
DOI10.1007/978-3-319-53925-6_33zbMATH Open1485.68308OpenAlexW2588896144MaRDI QIDQ2980930FDOQ2980930
Authors: Ei Ando 
Publication date: 5 May 2017
Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-53925-6_33
Recommendations
- Computing the Exact Distribution Function of the Stochastic Longest Path Length in a DAG
- Approximating the longest path length of a stochastic DAG by a normal distribution in linear time
- Bounding variance and expectation of longest path lengths in dags
- Algorithms to calculate the distribution of the longest path length of a stochastic activity network with continuous activity durations
- Long and short paths in uniform random recursive dags
- The Distribution of Path Lengths On Directed Weighted Graphs
- On approximating the longest path in a graph
- On approximating the longest path in a graph
- scientific article; zbMATH DE number 4060972
- Approximating the longest paths in grid graphs
Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Cites Work
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Directed tree-width
- Simulated annealing in convex bodies and an \(O^{*}(n^{4}\)) volume algorithm
- A deterministic polynomial-time approximation scheme for counting knapsack solutions
- A random polynomial-time algorithm for approximating the volume of convex bodies
- An FPTAS for #Knapsack and Related Counting Problems
- An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
- A geometric inequality and the complexity of computing volume
- Title not available (Why is that?)
- A fully polynomial-time approximation scheme for approximating a sum of random variables
- On the Complexity of Computing the Volume of a Polyhedron
- Bypassing KLS: Gaussian cooling and an \(O^\ast(n^3)\) volume algorithm
- Computing the volume is difficult
- An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution
- Computing the Exact Distribution Function of the Stochastic Longest Path Length in a DAG
Cited In (3)
This page was built for publication: An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2980930)
