Car routing solutions are omnipresent and solutions for pedestrians also exist.Furthermore,public or commercial buildings are getting bigger and the complexity of their internal structure has increased.Consequently,th...Car routing solutions are omnipresent and solutions for pedestrians also exist.Furthermore,public or commercial buildings are getting bigger and the complexity of their internal structure has increased.Consequently,the need for indoor routing solutions has emerged.Some prototypes are available,but they still lack semantically-enriched modelling (e.g.,access constraints,labels,etc.) and are not suitable for providing user-adaptive length-optimal routing in complex buildings.Previous approaches consider simple rooms,concave rooms,and corridors,but important characteristics such as distinct areas in huge rooms and solid obstacles inside rooms are not considered at all,although such details can increase navigation accuracy.By formally defining a weighted indoor routing graph,it is possible to create a detailed and user-adaptive model for route computation.The defined graph also contains semantic information such as room labels,door accessibility constraints,etc.Furthermore,one-way paths inside buildings are considered,as well as three-dimensional building parts,e.g.,elevators or stairways.A hierarchical structure is also possible with the presented graph model.展开更多
An efficient parallel global router using random optimization that is independent of net ordering is proposed.Parallel approaches are described and strategies guaranteeing the routing quality are discussed.The wire le...An efficient parallel global router using random optimization that is independent of net ordering is proposed.Parallel approaches are described and strategies guaranteeing the routing quality are discussed.The wire length model is implemented on multiprocessor,which enables the algorithm to approach feasibility of large scale problems.Timing driven model on multiprocessor and wire length model on distributed processors are also presented.The parallel algorithm greatly reduces the run time of routing.The experimental results show good speedups with no degradation of the routing quality.展开更多
In the first part of this- paper, three generalizations of arrangement graph A.,k of [1], namely Bn,k, Cn,k and Dn,k , are introduced. We prove that all the three classes of graphs are vertex symmetric, two of them ar...In the first part of this- paper, three generalizations of arrangement graph A.,k of [1], namely Bn,k, Cn,k and Dn,k , are introduced. We prove that all the three classes of graphs are vertex symmetric, two of them are edge symmetric. They have great faulty tolerance and high connectivity. We give the diameters of B..k and Cn,k, the Hamiltonian cycle of Cn,k and Hamiltonian path of B.,k. We list several open problems, one of them related to the complexity of sorting algorithm on the arrangement graphs. All these graphs can be thought as generalizations of star graph but are more flexible so that they can be considered as new interconnection network topologies. In the second part of this paper, we provide other four classes of combinatorial graphes, Chn , Cyn, Zhn and Zyn. Many good properties of them, such as high node--connectivity, node symmetry, edge symmetry, diameter, ets., are shown in this paper.展开更多
基金the Chair of GIScience,University of Heidelberg and the Klaus-Tschira Foundation (KTS) Heidelberg
文摘Car routing solutions are omnipresent and solutions for pedestrians also exist.Furthermore,public or commercial buildings are getting bigger and the complexity of their internal structure has increased.Consequently,the need for indoor routing solutions has emerged.Some prototypes are available,but they still lack semantically-enriched modelling (e.g.,access constraints,labels,etc.) and are not suitable for providing user-adaptive length-optimal routing in complex buildings.Previous approaches consider simple rooms,concave rooms,and corridors,but important characteristics such as distinct areas in huge rooms and solid obstacles inside rooms are not considered at all,although such details can increase navigation accuracy.By formally defining a weighted indoor routing graph,it is possible to create a detailed and user-adaptive model for route computation.The defined graph also contains semantic information such as room labels,door accessibility constraints,etc.Furthermore,one-way paths inside buildings are considered,as well as three-dimensional building parts,e.g.,elevators or stairways.A hierarchical structure is also possible with the presented graph model.
文摘An efficient parallel global router using random optimization that is independent of net ordering is proposed.Parallel approaches are described and strategies guaranteeing the routing quality are discussed.The wire length model is implemented on multiprocessor,which enables the algorithm to approach feasibility of large scale problems.Timing driven model on multiprocessor and wire length model on distributed processors are also presented.The parallel algorithm greatly reduces the run time of routing.The experimental results show good speedups with no degradation of the routing quality.
文摘In the first part of this- paper, three generalizations of arrangement graph A.,k of [1], namely Bn,k, Cn,k and Dn,k , are introduced. We prove that all the three classes of graphs are vertex symmetric, two of them are edge symmetric. They have great faulty tolerance and high connectivity. We give the diameters of B..k and Cn,k, the Hamiltonian cycle of Cn,k and Hamiltonian path of B.,k. We list several open problems, one of them related to the complexity of sorting algorithm on the arrangement graphs. All these graphs can be thought as generalizations of star graph but are more flexible so that they can be considered as new interconnection network topologies. In the second part of this paper, we provide other four classes of combinatorial graphes, Chn , Cyn, Zhn and Zyn. Many good properties of them, such as high node--connectivity, node symmetry, edge symmetry, diameter, ets., are shown in this paper.
