Treffer: The strongly connected reliability of complete digraphs: A branch-and-price algorithm for the capacitated \(p\)-median problem

Title:
The strongly connected reliability of complete digraphs: A branch-and-price algorithm for the capacitated \(p\)-median problem
Authors:
Manley Perkel, Zevi Miller, Dan Pritikin, Ivan Hal Sudborough
Source:
Networks. 45:165-168
Publisher Information:
Wiley, 2005.
Publication Year:
2005
Subject Terms:
vertex greedy algorithm, column generation, distributed match making, combinatorial number theory, 0211 other engineering and technologies, Directed graphs (digraphs), tournaments, connector, 0102 computer and information sciences, 02 engineering and technology, restricted cut, permuter, sparse switch, 7. Clean energy, 01 natural sciences, tournament scheme, Graph algorithms (graph-theoretic aspects), 0202 electrical engineering, electronic engineering, information engineering, dynamic greedy algorithm, 0101 mathematics, restricted edge-cut, Nonnumerical algorithms, integer programming, message complexity, Connectivity, Extremal problems in graph theory, algorithm, Network design and communication in computer systems, leader election, 4. Education, star graphs, sequential sum problem, Integer programming, superconnectivity, Programming involving graphs or networks, 16. Peace & justice, restricted sums, Branch-and-price, Column generation, p-median, branch-and-price, on-line Steiner tree problem, connectivity, Graph theory (including graph drawing) in computer science, Distributed algorithms, rearrangeable network, reachability
Document Type:
Fachzeitschrift Article
File Description:
application/xml
Language:
English
ISSN:
1097-0037
0028-3045
DOI:
10.1002/net.20060
DOI:
10.1002/net.20056
DOI:
10.1002/net.20052
DOI:
10.1002/net.20057
DOI:
10.1002/net.20058
DOI:
10.1002/net.20059
DOI:
10.1002/net.v45:3
Access URL:
http://www.cs.clemson.edu/~stabiliz/Papers/networks2005.pdf
https://zbmath.org/2173325
https://doi.org/10.1002/net.20059
https://zbmath.org/2173324
https://doi.org/10.1002/net.20058
https://zbmath.org/2173326
https://doi.org/10.1002/net.20057
https://zbmath.org/2173328
https://doi.org/10.1002/net.20052
https://zbmath.org/2173327
https://doi.org/10.1002/net.20060
https://dblp.uni-trier.de/db/journals/networks/networks45.html#MillerPPS05
http://www.users.miamioh.edu/millerz/pdf/sequentialSum.pdf
https://onlinelibrary.wiley.com/doi/abs/10.1002/net.20057
https://umu.diva-portal.org/smash/record.jsf?pid=diva2:665017
https://dblp.uni-trier.de/db/journals/networks/networks45.html#BaltzJS05
http://www.diva-portal.org/smash/record.jsf?pid=diva2:665017
https://onlinelibrary.wiley.com/doi/10.1002/net.20058
https://api.wiley.com/onlinelibrary/tdm/v1/articles/10.1002%2Fnet.20059
https://dblp.uni-trier.de/db/journals/networks/networks45.html#BrownL05
https://onlinelibrary.wiley.com/doi/abs/10.1002/net.20060
https://www.cs.clemson.edu/stabiliz/Papers/networks2005.pdf
http://www.scs.carleton.ca/~santoro/LeaderStar.pdf
http://onlinelibrary.wiley.com/doi/10.1002/net.20052/abstract
http://www.cs.clemson.edu/stabiliz/Papers/networks2005.pdf
https://dblp.uni-trier.de/db/journals/networks/networks45.html#ShiBS05
https://people.scs.carleton.ca/~santoro/LeaderStar.pdf
Rights:
Wiley Online Library User Agreement
Accession Number:
edsair.doi.dedup.....f4561fc7bb08304d72bc05d5c5cc2b3d
Database:
OpenAIRE

Weitere Informationen

Given a digraph D, consider the model where each vertex is always operational, but the edges are independently operational with probability p. The strongly connected reliability of D, scRel(D,p), is the probability that the spanning subgraph of D consisting of the operational edges is strongly connected. One can view strongly connected reliability as the probability that any vertex can send information to any other vertex, given that edges fail independently. There are very few classes for which there is an efficient algorithm for calculating the strongly connected reliability. This article presents the fist polynomial time algorithm for computing the strongly connected reliability of complete digraphs, that is, digraphs in which every vertex is joined to every other vertex by exactly one edge (one in each direction). © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(3), 165–168 2005