6533b7cffe1ef96bd1258467
RESEARCH PRODUCT
An efficient algorithm for stopping on a sink in a directed graph
Grzegorz KubickiGrzegorz KubickiWayne GoddardEwa Kubickasubject
Factor-critical graphDiscrete mathematicsApplied MathematicsNeighbourhood (graph theory)Directed graphManagement Science and Operations ResearchBiconnected graphIndustrial and Manufacturing EngineeringHypercube graphCombinatoricsWheel graphPath graphGraph factorizationSoftwareMathematicsofComputing_DISCRETEMATHEMATICSMathematicsdescription
Abstract Vertices of an unknown directed graph of order n are revealed one by one in some random permutation. At each point, we know the subgraph induced by the revealed vertices. Our goal is to stop on a sink, a vertex with no out-neighbors. We show that if a sink exists this can be achieved with probability Θ ( 1 / n ) , which is best possible.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2013-05-01 | Operations Research Letters |