Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>A maximal uni-connected subgraph (I refuse to call them "components", because the underlying relation is not transitive) contains all or none of a strongly connected component. As a first step in enumerating maximal uni-connected subgraphs, then, collapse each SCC to a single vertex (i.e., compute the condensation of the input graph).</p> <p>A uni-connected subgraph of an acyclic directed graph has the property that, for distinct nodes u and v, either there is a path from u to v, or a path from v to u, but not both. Write u &lt; v if there is a path from u to v and u != v. Since either u &lt; v or v &lt; u but not both, and u &lt; v and v &lt; w implies u &lt; w, the relation &lt; is a strict total order. By sorting the vertices in the subgraph, we find that they lie on a single path. This path is maximal if and only if no vertex can be inserted, which means that it begins at a source (no incoming edges), ends at a sink (no outgoing edges), and is comprised solely of edges that appear in the <a href="http://en.wikipedia.org/wiki/Transitive_reduction" rel="nofollow">transitive reduction</a> of the acyclic directed graph.</p> <p>Here is one algorithm for enumerating maximal uni-connected subgraphs of a directed graph G.</p> <ol> <li>Find the strong components of G. Contract them, yielding the condensation G'.</li> <li>Compute the transitive reduction G'' of G'.</li> <li>Enumerate all source-sink paths by, e.g., depth-first search, then replace each node by its strong component in G.</li> </ol> <p>Here is a graph family with exponentially many maximal uni-connected subgraphs. All edges are directed downward.</p> <pre><code> * / \ * * \ / * / \ * * \ / * / \ . . . \ / * / \ * * \ / * </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POFinding a different sort of connected component
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USDavid Eisenstat
    1. USDavid Eisenstat
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POFinding a different sort of connected component
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThank you. So I understand, step 2 takes cubic time in practice? What is the worst case complexity of step 3?
      singulars
      1. PO
      1. USphoenix
    2. CO@phoenix Exponential, but only since there can be exponentially many uni-connected subgraphs (see my edited answer for an example). Each one costs poly-time to output.
      singulars
      1. PO
      1. USDavid Eisenstat
    3. COFor any graph the minimum number of maximal uni connected subgraphs that cover every node is always linear though surely. It would be helpful to be able to output such a minimal covering. That is what I had in mind. How much is poly time in your algorithm assuming cubic for step two?
      singulars
      1. PO
      1. USphoenix
 

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