Estimating the Number of s-t Paths in a Graph

DOI10.7155/JGAA.00142MaRDI QIDQ5301411zbMATH OpenOpenAlexWikidataFDO

Authors Ben Roberts, Dirk P. Kroese

Publication date 19 January 2009

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL http://www.emis.de/journals/JGAA/accepted/2007/RobertsKroese2007.11.1.pdf

zbMATH Keywords

random graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Approximately Counting Hamilton Paths and Cycles in Dense Graphs
• Fast sequential importance sampling to estimate the graph reliability polynomial
• A LOWER BOUND OF THE EXPECTED MAXIMUM NUMBER OF VERTEX-DISJOINT s-t PATHS ON PROBABILISTIC GRAPHS
• On the number of paths and cycles for almost all graphs and digraphs
• Stochastic enumeration method for counting trees

Cited in

(8)

• On sampling simple paths in planar graphs according to their lengths
• Exact localisations of feedback sets
• Stochastic enumeration method for counting NP-hard problems
• Generalized bounded rationality and robust multicommodity network design
• Methods for determining cycles of a specific length in undirected graphs with edge weights
• On the estimate of the size of a directed graph
• Cognitively-constrained learning from neighbors
• On computing the path number of a graph

This page was built for publication: Estimating the Number of s-t Paths in a Graph

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