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_33MaRDI QIDQ2980930zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 3980484 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A deterministic polynomial-time approximation scheme for counting knapsack solutions
• A fully polynomial-time approximation scheme for approximating a sum of random variables
• A geometric inequality and the complexity of computing volume
• A random polynomial-time algorithm for approximating the volume of convex bodies
• An FPTAS for #Knapsack and Related Counting Problems
• An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution
• An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
• Bypassing KLS: Gaussian cooling and an \(O^\ast(n^3)\) volume algorithm
• Computing the Exact Distribution Function of the Stochastic Longest Path Length in a DAG
• Computing the volume is difficult
• Directed tree-width
• On the Complexity of Computing the Volume of a Polyhedron
• Simulated annealing in convex bodies and an \(O^{*}(n^{4}\)) volume algorithm

Cited in

(3)

• Computing the Exact Distribution Function of the Stochastic Longest Path Length in a DAG
• Bounding variance and expectation of longest path lengths in dags
• Approximating the longest path length of a stochastic DAG by a normal distribution in linear time

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)