![]() |
.. (לתיקייה המכילה) | |
In question 5, can I assume I get a non-standard graph representation? For example, can I assume I get an adjacency matrix with an array of out-degrees and in-degrees of vertices? | |
You may not assume such a representation for 2 reasons: 1) It trivializes the question. 2) Given a standard representation, calculating the above would require little omega of n time, and would therefore yield an algorithm whose running time is also little omega of n (not what you want). Any addition to the graph representation which can be calculated in time which would still yield an optimal algorithm is acceptable (explain how it is calculated from the standard representation, if you do use such additional information) |