Computing the Exact Distribution Function of the Stochastic Longest Path Length in a DAG

DOI10.1007/978-3-642-02017-9_13MaRDI QIDQ3630194zbMATH OpenOpenAlexFDO

Authors Ei Ando, Hirotaka Ono, Kunihiko Sadakane, Masafumi Yamashita

Publication date 3 June 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02017-9_13

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Recommendations

• Approximating the longest path length of a stochastic DAG by a normal distribution in linear time
• An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths
• 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
• Longest path distance in random circuits

Cited in

(5)

• Algorithms to calculate the distribution of the longest path length of a stochastic activity network with continuous activity durations
• An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths
• Longest path distance in random circuits
• 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: Computing the Exact Distribution Function of the Stochastic Longest Path Length in a DAG

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