China
Africa
Explore chapters and articles related to this topic
Uniform delivery in group communication
Published in Uri Abraham, Models for Concurrency, 2020
The Early Delivery predicate and operation deliverable and deliver will be defined here and proved to satisfy the four requirements of data buffers. If B is a Data_Buffer, let F = fish(B) be its fish. Define deliverable(B) iff F is a deliverable fish, and in that case let i1, …, id be the set of deliverable processes, and define deliver(B) as the sequence of messages formed from the set {mi1,…,mid} ordered by some topological sorting algorithm that extends →. (See the corresponding discussion in subsection 1.3.)
Computer Assembly Planners in Manufacturing Systems and Their Applications in Aircraft Frame Assemblies
Published in Cornelius Leondes, The Design of Manufacturing Systems, 2019
Roy et al. [32] proposed a design environment which acts as a preprocessing step before the actual assembly operation. The assembly is first modeled using the modified functional relationship graph (M-FRG) that captures the functional relationships between components or subassemblies. A procedure is then used for the generation of a second-order relationship graph (R2), which specifies the temporal relationships among the relationships specified in M-FRG. Subsequently, a topological sorting algorithm is applied to the R2 graph to give a topological order of mating relationships. A directed assembly tree is finally created by using the information available from the topological ordering of nodes in the R2 graph and the R2 graph itself.
Floorplanning: Early Research
Published in Charles J. Alpert, Dinesh P. Mehta, Sachin S. Sapatnekar, Handbook of Algorithms for Physical Design Automation, 2008
Another constraint-based floorplanning algorithm proposed by Vijayan et al. [50] also can handle flexible, fixed (rigid), and preplaced modules. The input is specified as two sets of constraints in the form of the two directed acyclic horizontal and vertical constraint graphs. A linear time algorithm for topological sorting of directed acyclic graphs is used to find the critical (longest) paths in the two graphs. Redundant constraints are removed and flexible blocks on the more critical paths are reshaped. Certain criteria to characterize two different notions of redundancy among constraints are formulated and utilized to reduce the time complexity. This heuristic is iterated until a floorplan solution of desired dimensions is obtained.
Global exponential stabilisation of acyclic traffic networks
Published in International Journal of Control, 2019
Maria Kontorinaki, Iasson Karafyllis, Markos Papageorgiou
(a) From a graph-theoretic point of view, directed acyclic graphs are graphs whose vertices can admit a topological sorting. This means, that their vertices can be ordered in such a way, that the starting endpoint of every edge (joining two vertices) occurs earlier in the ordering than the ending endpoint of the edge. Assigning the vertices of the graph to the components or cells of the network, for any given acyclic network, and by using the previous definition, we are in a position to reorder the cells of the network into a topological sorting. The main consequence of this sorting is that the matrix P = {pi, j: i, j = 1, …, n} ∈ [0, 1]n × n containing the turning rates of the network becomes strictly upper triangular (Godsil & Royle, 2013; Kim, 1979, 1982). (b) The necessity of Assumption (H2) is a consequence of our goal for global stabilisation of the network: for global stability results we need to exclude cases that are not controllable via inflow control. Proposition 3.1 in the following section shows that the existence of cycles is incompatible with the existence of a globally stabilising feedback.
Order-of-addition experiments: A review and some new thoughts
Published in Quality Engineering, 2019
A topological sorting exists if and only if the directed graph is acyclic. For example, j preceding k, k preceding l, and l preceding j cannot be simultaneously identified as favorable. In the presence of cycles, more advanced algorithms are needed to speculate the optimal order(s). This will be investigated in the future. A possible approach is to “break” the cycles using existing tools in computer science, such as Tarjan (1972)’s strongly connected components algorithm.