Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Do you mind a probabilistic solution? That is, it won't guarantee finding all of the vertices, but it usually does first try, and is overwhelmingly likely to after 2 or 3 tries?</p> <p>If you're OK with that, randomly assign every edge a resistance, and solve for the voltages of every node if you put the source at a voltage of 1 and the sink at a voltage of 0. Any edge where the two nodes connecting it are at different voltages is clearly on a simple path (the path is easy to construct, just go through ascending voltages from one end, and descending from the other). An edge where the two nodes connecting it are at the same voltage is extremely <em>unlikely</em> to be on a simple path, though that theoretically can happen.</p> <p>Repeat with several randomly assigned sets of resistances, and you're overwhelmingly likely to have found all edges that are on simple paths. (You haven't proven this answer, but the odds of being wrong are vanishingly small.)</p> <p>Of course once you know all of the edges that are on simple paths, it is trivial to get all of the vertices that are on simple paths.</p> <p><strong>Update</strong></p> <p>I believe that the following is true, but have no proof. Suppose that we take a set of resistances and work out voltages. For every edge which is in a simple path, there is another edge (maybe the same) such that varying the resistance of only that edge will cause the voltage across the first edge to vary. If so, it is possible in polynomial time to identify every edge in a simple path.</p> <p>Intuitively it makes sense to me, but I have no idea how I would prove it.</p>
    singulars
    1. This table or related slice is empty.
    1. POFind all *vertices* on all simple paths between two vertices in an undirected graph
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USbtilly
    1. USbtilly
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload