Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Interval_(graph_theory)> ?p ?o }
Showing triples 1 to 32 of
32
with 100 triples per page.
- Interval_(graph_theory) abstract "In graph theory, an interval I(h) in a directed graph is a maximal, single entry subgraph in which h is the only entry to I(h) and all closed paths in I(h) contain h. Intervals were described in 1976 by F. E. Allen and J. Cooke. Interval graphs are integral to some algorithms used in compilers, specifically data flow analyses.The following algorithm finds all the intervals in a graph consisting of vertices N and the entry vertex n0, and with the functions pred(n) and succ(n) which return the list of predecessors and successors of a given node n, respectively. H = { n0 } // Initialize work list while H is not empty remove next h from H create the interval I(h) I(h) += { h } while ∃n ∈ { succ(I(h)) — I(h) } such that pred(n) ⊆ I(h) I(h) += { n } while ∃n ∈ N such that n ∉ I(h) and // find next headers ∃m ∈ pred(n) such that m ∈ I(h) H += n The algorithm effectively partitions the graph into its intervals. Each interval can in turn be replaced with a single node, while all edges between nodes in different intervals in the original graph become edges between their corresponding nodes in the new graph. This new graph is called an interval derived graph. The process of creating derived graphs can be repeated until the resulting graph can't be reduced further. If the final graph consists of a single node, then the original graph is said to be reducible.".
- Interval_(graph_theory) wikiPageID "39034538".
- Interval_(graph_theory) wikiPageLength "2927".
- Interval_(graph_theory) wikiPageOutDegree "9".
- Interval_(graph_theory) wikiPageRevisionID "678491574".
- Interval_(graph_theory) wikiPageWikiLink Category:Control-flow_analysis.
- Interval_(graph_theory) wikiPageWikiLink Category:Graph_theory_objects.
- Interval_(graph_theory) wikiPageWikiLink Compiler.
- Interval_(graph_theory) wikiPageWikiLink Compilers.
- Interval_(graph_theory) wikiPageWikiLink Directed_graph.
- Interval_(graph_theory) wikiPageWikiLink F._E._Allen.
- Interval_(graph_theory) wikiPageWikiLink Frances_E._Allen.
- Interval_(graph_theory) wikiPageWikiLink Graph_theory.
- Interval_(graph_theory) wikiPageWikiLink Natural_loop.
- Interval_(graph_theory) wikiPageWikiLink Partition_of_a_set.
- Interval_(graph_theory) wikiPageWikiLink Path_(graph_theory).
- Interval_(graph_theory) wikiPageWikiLinkText "Interval (graph theory)".
- Interval_(graph_theory) hasPhotoCollection Interval_(graph_theory).
- Interval_(graph_theory) wikiPageUsesTemplate Template:About.
- Interval_(graph_theory) wikiPageUsesTemplate Template:Cite_journal.
- Interval_(graph_theory) wikiPageUsesTemplate Template:Dubious.
- Interval_(graph_theory) wikiPageUsesTemplate Template:Reflist.
- Interval_(graph_theory) subject Category:Control-flow_analysis.
- Interval_(graph_theory) subject Category:Graph_theory_objects.
- Interval_(graph_theory) hypernym Maximal.
- Interval_(graph_theory) comment "In graph theory, an interval I(h) in a directed graph is a maximal, single entry subgraph in which h is the only entry to I(h) and all closed paths in I(h) contain h. Intervals were described in 1976 by F. E. Allen and J. Cooke.".
- Interval_(graph_theory) label "Interval (graph theory)".
- Interval_(graph_theory) sameAs m.0swkn48.
- Interval_(graph_theory) sameAs Q17092623.
- Interval_(graph_theory) sameAs Q17092623.
- Interval_(graph_theory) wasDerivedFrom Interval_(graph_theory)?oldid=678491574.
- Interval_(graph_theory) isPrimaryTopicOf Interval_(graph_theory).