A linear time algorithm for computing the most reliable source on a series--parallel graph with unreliable edges

DOI10.1016/S0304-3975(97)00124-2zbMath0915.68081OpenAlexW2072715079MaRDI QIDQ1274933

Charles J. Colbourn, Guoliang Xue

Publication date: 12 January 1999

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(97)00124-2

zbMATH Keywords

algorithmstime complexityseries-parallel graphnetwork reliabilitypartial 2-trees

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Related Items (10)

On the Parameterized Complexity of the Expected Coverage Problem ⋮ On the parameterized complexity of the expected coverage problem ⋮ A DIVIDE-AND-CONQUER ALGORITHM FOR FINDING A MOST RELIABLE SOURCE ON A RING-EMBEDDED TREE NETWORK WITH UNRELIABLE EDGES ⋮ Multiple facility location on a network with linear reliability order of edges ⋮ A method to calculate the number of spanning connected unicyclic(bicyclic) subgraphs in 2-separable networks ⋮ A linear time algorithm for computing a most reliable source on a tree network with faulty nodes ⋮ The approximability of multiple facility location on directed networks with random arc failures ⋮ Nonexistence of uniformly most reliable two-terminal graphs ⋮ Network location of a reliable center using the most reliable route policy ⋮ An Edge-Turbulence Algorithm for the 2-MRS Problem on Trees with Unreliable Edges

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On simple characterizations of k-trees
• The Maximal Expected Covering Location Problem: Revisited
• Steiner trees, partial 2–trees, and minimum IFI networks
• Networks immune to isolated failures
• Reliability covering problems
• Location of facilities on a network subject to a single‐edge failure
• The Maximum Availability Location Problem
• A single facility location problem on a tree with unreliable edges
• A Reliability Model Applied to Emergency Service Vehicle Location
• Locating A Broadcast Facility In An Unreliable Network

This page was built for publication: A linear time algorithm for computing the most reliable source on a series--parallel graph with unreliable edges