Browsing by Author "Nakajima, Kazuo"
Now showing 1 - 6 of 6
Results Per Page
Sort Options
Item Adaptive Diagnosis for Probabilistically Diagnosable Systems.(1989) Shih, Feng-Hsien Warren; Nakajima, Kazuo; ISRWe show that the adaptive diagnosis approach can be applied to probabilistically diagnosable systems. Three adaptive diagnosis algorithms are developed under both the symmetric and asymmetric test invalidation assumptions. A test selection strategy based on a probabilistic measure of test results is derived and used in each algorithm. We show that the adaptive algorithms are efficient in identifying all faulty units in a system.Item Crossing Minimization in the Straight-Line Embedding of Graphs.(1987) Masuda, Sumio; Nakajima, Kazuo; Kashiwabara, Toshinobu; Fujisawa, Toshio; ISRThe problem of embedding a graph in the plane with the minimum number of edgecrossings arises in some circuit layout problems. It has been known that this problem is in general NP-hard. An interesting and relevant problem in the area of book embedding was recently shown to be NP-hard. This result implies that the former problem is NP-hard even when the vertices are placed on a straight line l and the edges are drawn completely on either side of l. In this paper, we show that the problem remains NP-hard even if, in addition to these constraints, the positions of the vertices on SCRIPT l are predetermined.Item Graph Bipartization and Via Minimization.(1987) Choi, Hyeong-Ah; Nakajima, Kazuo; Rim, Chong S.; ISRThe vertex- (resp., edge-) deletion graph bipartization problem is the problem of deleting a set of vertices (resp., edges) from a graph so as to make the remaining graph bipartite. In this paper, we first show that the vertex-deletion graph bipartization problem has a solution of size k or less if and only if the edge- deletion graph bipartization problem has a solution of size k or less, when the maximum vertex degree is limited to three. This immediately implies that (1) the vertex-deletion graph bipartization problem is NP-complete for cubic graphs, and (2) the minimum vertex-deletion graph bipartization problem is solvable in polynomial time for planar graphs when the maximum vertex degree is limited to three. We then prove that the vertex- deletion graph bipartization problem is NP-complete for planar graphs when the maximum vertex degree exceeds three. Using this result, we finally show that the via minimization problem, which arises in the design of integrated circuits and printed circuit boards, is NP-complete even when the maximum "junction" degree is limited to four.Item Logic Foundry: A Rapid Prototyping Tool for FPGA-based DSP Systems(2002-05-22) Spivey, G.; Bhattacharyya, S. S.; Nakajima, KazuoNo abstact submitted. (Also UMIACS-TR-2002-29)Item An NP-Hard Crossing Minimization Problem for Computer Network Layout.(1986) Masuda, Sumio; Kashiwabara, Toshinobu; Nakajima, Kazuo; Fujisawa, Toshio; ISRA layout problem of computer communication network is formulated graph-theoretically as follows: "Given a simple graph G = (V,E), find an embedding of G with the minimum number of edge-crossings such that (i) the vertices in V are placed on the circumference of a circle C, and (ii) the edges in E are drawn only inside C." In this paper, this problem will be shown to be NP-hard. Therefore, it is very likely to be intractable.Item Reconfiguration for Programmable ASIC Arrays(1992) Narasimhan, Jagannathan; Nakajima, Kazuo; Rim, Chong S.; Dahbura, Anton T.; ISRIn an approach recently proposed for the yield enhancement of programmable gate arrays (PGAs), an initial placement of a circuit is first obtained using a standard technique such as simulated annealing on a defect-free PGA. In the next step this placement is reconfigured so that the circuit is mapped onto the defect-free portion of a defective PGA chip with the same architecture. We first provide a graph theoretical formulation of the reconfiguration aspect of this approach. Based upon this formulation, we present three efficient algorithms. The first one optimally reconfigures the I/O buffers located on the periphery of a programmable array. The remaining algorithms are used as heuristics to reconfigure the gates located within a PGA and the processors within wafer scale integrated processor array. We evaluate the heuristic algorithms using the measure of routability and total wire length of the reconfigured placement of the circuit. Based on this evaluation, we establish good reconfiguration strategies.