China
Africa
Explore chapters and articles related to this topic
Packing Floorplan Representations
Published in Charles J. Alpert, Dinesh P. Mehta, Sachin S. Sapatnekar, Handbook of Algorithms for Physical Design Automation, 2008
Tung-Chieh Chen, Yao-Wen Chang
Let Gh(Vh, Eh) be the horizontal unit adjacency graph. For each vertex u ∈ Vh, lh(u) denotes the length of the longest path from the source sh to u. Similarly in Gv, lv(u) denotes the longest path length from sv to u ∈ Vv. We use a longest-path algorithm to determine the positions of modules. The longest-path algorithm works in linear time of the number of edges when the input G is a directed acyclic graph. The total number of edges of the unit adjacency graphs is between 2(pq + p + q) and 2(pq + p + q) – 4. So, the time complexity to find the longest path is O(pq).
Network Analysis
Published in Michael W. Carter, Camille C. Price, Ghaith Rabadi, Operations Research, 2018
Michael W. Carter, Camille C. Price, Ghaith Rabadi
If we inspect the previous dual formulation, we can see that the constraints require that one unit of flow is to be routed from node 1 to node 5. We now recognize that this is the specialized form of the transshipment model that we dealt with in Section 3.5 to find the shortest path through a network. In our project management application, however, we minimize project duration by maximizing the path length. We can therefore treat our project scheduling problem as a longest path problem.
Performance Modeling and Analysis Using VHDL and SystemC
Published in Wai-Kai Chen, Computer Aided Design and Design Automation, 2018
Robert H. Klenke, Jonathan A. Andrews, James H. Aylor
Performing a search with the restriction that no arc is contained in the path more than once requires maintaining information on arcs being added or removed from the path. Maintaining this information during the search makes the algorithm and its implementation much more complicated relative to the search for the longest path with no repeated nodes. Therefore, a novel approach to this problem was developed. The approach used is to map the problem to the problem of searching for the longest path with no repeated nodes. This mapping can be accomplished by transforming the digraph to a new digraph, to be referred to as the transformed digraph (or Tdigraph). Given a digraph, G(V, E), which consists of a set of nodes V = {v1, v2,..., vk} and a set of arcs E = {e1, e2,..., el} the transformation τ maps G(V, E) into a Tdigraph TG(N, A), where N is its set of nodes and A its set of arcs. The transformation is defined as τ(G(V, E)) = TG(N, A), and contains the following steps:Step 1. ∀(ei ∈ E) generate a node ni ∈ N.Step 2. ∀(v ∈ V) and ∀(ep∈dinv,eq∈doutv) generate an arc a ∈ A such that a: np → nq.
On the index of convergence of a class of Boolean matrices with structural properties
Published in International Journal of Control, 2021
Guilherme Ramos, Sérgio Pequito, Carlos Caleiro
Next, we review some problems on the digraphs described above. The shortest path problem is the problem of finding a minimum length path between two vertices s and t, which we refer to as the source and target, respectively. The problem of finding the path with a maximum length between source and target in is the longest path problem, which we shall denote by . Computationally, we may solve the shortest path problem in polynomial time (Cormen, Leiserson, Rivest, & Stein, 2001). The longest path problem is known to be NP-hard (Schrijver, 2003), but it has a linear time solution when we consider DAGs (Sedgewick & Wayne, 2011).
Efficient algorithm to find makespan in manufacturing systems under multiple scheduling perturbations
Published in International Journal of Production Research, 2018
Golshan Madraki, Robert P. Judd
The longest path or critical path has been studied in graph-based manufacturing problems previously (Sotskov and Gholami 2017). The longest path in a DAG is a path with the maximum cumulative weight found by the summation of the node weights along the path from any first node to any last node. To calculate the longest path, the Standard Longest Path Algorithm (SLPA) is considered. In the SLPA, first, the nodes are topologically sorted, then, Dynamic Programming is utilised to find the longest path among the sorted nodes. This solution takes a linear time with respect to the number of nodes and edges in the DAG (Lawler 1976).
A theoretical framework to accelerate scheduling improvement heuristics using a new longest path algorithm in perturbed DAGs
Published in International Journal of Production Research, 2023
Golshan Madraki, Seyedamirabbas Mousavian, Yasamin Salmani
The longest path problem has been used in several research fields including route planning, logistics, supply chain, and scheduling problems (Feng et al. 2021; Yachai et al. 2021). The longest path problem in DAG can refer to either deterministic problem where the weights of the nodes are deterministic (C. Wang, Wang, and Cheung 2021; Q. Wang et al. 2015), or probabilistic with the random value for the weight of nodes (Canon and Jeannot 2016; Murat and Paschos 1999). This paper focuses on the deterministic longest path problem in a DAG since in our classical scheduling problem the processing time of all operations is assumed to be deterministic.