Postagens

Push-relabel algorithm

Imagem
The following image illustrates a partially executed flow graph and the Push-Relabel algorithm, with the respective residual graph displayed on the right. The algorithm followed a FIFO order of selecting nodes and then selected nodes by alphabetical order when they were simultaneously activated. Active nodes are the ones that have excess in the pre-flow.  Based on the process illustrated, mark the correct alternative of the next step in the algorithm: a) Relabeling of ' c ', transforming 'h' to 2, and returning the excess flow to ' b ' using Push. b) Relabeling of ' a ', transforming 'h' to 8, and returning the excess flow to ' S ' using Push. c) Relabeling of ' c ', transforming 'h' to 8, and returning the excess flow to ' S ' using Push. d) Relabeling of ' e ', transforming 'h' to 1, and pushing the excess flow to ' t '. e) None of the above     Original idea  by: Giorgio Rossa
2 comentários
Leia mais

Kosaraju-Sharir’s algorithm and SCC Question

 The Kosaraju-Sharir’s algorithm is usually used to find strongly connected components in a graph. Analyze which options below are valid tasks to use the algorithm, and mark the alternative with the correct options.  I. Validate and sort a sequence of actions which depend on each other, to make sure that prerequisites of a task can be completed before the given task is performed. II. Group classes of a given Object-Oriented solution to isolate packages, in a graph where each class is a node and classes with any interaction have an edge.  III. Find the maximum number of processing steps of a given algorithm, in a graph where each algorithm step was considered as a node. IV.  Identify deadlocks in the operating system process execution, in a graph where nodes are processes and edges are created between processes when one waits the other for resources. V. Optimize code compilation, identifying and removing code parts that are unreachable or adding paralleliz...
1 comentário
Leia mais

Questão BFS/DFS

Imagem
  Analyze the statements below, knowing that DFS and BFS algorithms start in the node "a" and the adjacency list is sorted in alphabetical order.   I.  During a BFS execution, three nodes that are already visited are verified (thus not being visited again); II. There is one back edge in the graph; III. If we remove the edges  C D  and EF,  the resulting graph is a bipartite graph; IV. The DFS execution would restart twice in this graph, creating two different trees; The correct statements are:  a) I and III b) Only II c) II and III d) I, II and IV e) None of the above   Original idea  by: Giorgio Rossa     
2 comentários
Leia mais