China
Africa
Explore chapters and articles related to this topic
Basic Data Structures
Published in Charles J. Alpert, Dinesh P. Mehta, Sachin S. Sapatnekar, Handbook of Algorithms for Physical Design Automation, 2008
The mathematical structure that comes closest to representing a circuit is the hypergraph. A hypergraph consists of a set of vertices and a set of hyperedges, where each hyperedge connects a set of k ≥ 2 vertices. (When k = 2 for each edge, the hypergraph reduces to the more familiar graph.) A hypergraph approximates a circuit in that each vertex is mapped to a component and each hyperedge corresponds to a net. Even so, the hypergraph is not a complete representation of a circuit: Components may have associated physical attributes. For example, if the component is a rectangle, its height and width will be provided; locations of pins on the rectangle may also be provided.Nets have an associated direction, which play a role during routing. Consider Net 1 in Figure 4.1 that interconnects three terminals. Pin A is the source of the signal and C1.in1 and C2.in1 are the sinks.Nets connect pins, but hyperedges connect components. You could fix this by having vertices model pins rather than components, but then you lose the property that some pins are associated with a single component. If this component is moved, all of its pins must move with it.
Introduction
Published in Vlad P. Shmerko, Svetlana N. Yanushkevich, Sergey Edward Lyshevski, Computer Arithmetics for Nanoelectronics, 2018
Vlad P. Shmerko, Svetlana N. Yanushkevich, Sergey Edward Lyshevski
Recursive minimum-cut placement. The problem of recursive minimum-cut placement is stated by representing the logic network as a hypergraph. A hypergraph is like an undirected graph, but each hyperedge, rather than connecting two vertices, connects an arbitrary subset of vertices. The components correspond to the nodes, and the nets correspond to the hyperedges connecting these components (nodes). A decomposition of the logic network into two subnetworks is formulated as the problem of finding a balanced bipartition of the hypergraph with minimal cuts. This problem is also known as the balanced hypergraph bipartition problem.
Software Integrated Framework Design for IoT-Based Applications
Published in Monideepa Roy, Pushpendu Kar, Sujoy Datta, Interoperability in IoT for Smart Systems, 2020
Sugyan Kumar Mishra, Anirban Sarkar
HC is an assignment of colors (positive integer) to the vertices of the hypergraph so that the vertices of every hyperedge contain each color from the color set. The minimum number of colors is required to color the vertices of the hypergraph, known as the chromatic number (χ(H)) of a hypergraph [42].
A hierarchical perception decision-making framework for autonomous driving
Published in Cyber-Physical Systems, 2022
Ende Zhang, Jin Huang, Yue Gao, Yau Liu, Yangdong Deng
With the extracted environmental information, the essential task is how to integrate multi-modality environmental information, capture the complex relationship between the current driving environment and historical driving experience data, and use relational reasoning and combination generalisation to support decision-making. Here we employ hypergraph neural networks [23] to model the corrilation of driving data. Hypergraphs are extensions of graphs by allowing a hyperedge to connect more than two nodes. A hypergraph is composed of a vertex set , a hyperedge set , and a weight set defined over the hyperedges . The hypergraph can be represented as a incidence matrix , with each entry defined as
Most-intersection of countable sets
Published in Journal of Applied Non-Classical Logics, 2021
An important application of the most-intersection operator turns out to be related with the problem of determining the average behaviour of a discrete system, whether the system is of finite or infinite size. We shall consider discrete evolutionary systems, meaning that the evolution is carried in discrete stages. By evolution we mean any system which can be represented by graphs and the neighbourhood relation. So what we mean by a system is really a graph having some neighbourhood relations among its vertices. But what about the representation of these systems? An evolutionary system of this kind can be thought to be given in the form of a hypergraph. Hypergraph is a generalisation of a standard graph except that the edge relation is not restricted to two vertices like in standard graphs where the edge relation is strictly between the two vertices of the graph. For a detailed account on hypergraphs, we refer the reader to Bretto (2013). However let us now give some definitions that we need for our work.
Stabilising quasi-time-optimal nonlinear model predictive control with variable discretisation
Published in International Journal of Control, 2022
Christoph Rösmann, Artemi Makarow, Torsten Bertram
The local and the global uniform grid reveal different sparsity patterns due to their optimisation structure. This is also immediately visible in its hypergraph representation as introduced for MPC in Rösmann et al. (2018). A hypergraph is a graph composed of a set of vertices and a set of hyperedges. Hyperedges connect an arbitrary number of vertices rather than only pairs of vertices compared to regular graphs. For nonlinear programmes (13) and (14), each vertex refers to an optimisation parameter, i.e. , or . A hyperedge refers to cost or constraint terms and is only connected to the nodes on which they directly depend. Figure 3 shows the hypergraph for the global uniform grid (13) and Figure 4 for the local uniform grid (14). Trivial substitutions for optimisation parameters like are not represented by a dedicated edge as these parameters are not subject to optimisation. These vertices are called fixed which is indicated by a double circle. Also lower and upper bounds for optimisation parameters are directly cached in their vertices. Note that parameter in Figure 3 is connected with all edges for adhering to the system dynamics. This indicates a dense column in the constraint Jacobian respectively a dense row and column in the Hessian of the Lagrangian (see Figure 5(a)). In contrast, the hypergraph for the local uniform grid (14) contains more vertices, but the maximum number of connected vertices for each edge is limited and independent of N. Figure 5(b) shows an example for the corresponding structure of the Hessian of the Lagrangian in which the percentage of non-zeros (nz) is smaller.