CMPUT272 Lecture Notes - Lecture 23: Directed Acyclic Graph, Covering Relation, Transitive Reduction

38 views3 pages
November 27 2014
ETLC 2-001
Partial order may be represented as a directed graph. (no cycles)
Transitive closure
Given any directed acyclic graph G,
G: u -> v -> w -> x
Now, u -> w, u -> x, v -> x
Also, u -> u, v -> v, w -> w, and x -> x
Computed via 'matrix multiplication'
[ u v w x ] * [ u ]
[ v ]
[ w ]
[ x ]
Time proportional to n^3,
( Strassen '69 managed O(n^2.81) )
( '90 managed O(n^2.375) )
( Williams '13 managed O(n^2.3727) )
Goal: O(n^2)
Transitive reduction
Only: u -> v -> w -> x
Corrosponds to the 'covering relation' which is the haas
diagram.
which, is unique.
Closure and reduction, represesents 'reachability'
Counting
Unlock document

This preview shows page 1 of the document.
Unlock all 3 pages and 3 million more documents.

Already have an account? Log in

Get access

Grade+20% OFF
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers