2024-10-03T16:40:30Z
https://nagoya.repo.nii.ac.jp/oai
oai:nagoya.repo.nii.ac.jp:00013167
2023-01-16T04:00:15Z
320:321:322
An Improved Algorithm for the Net Assignment Problem
ONO, Takao
HIRATA, Tomio
open access
Copyright (C) 2001 IEICE
logic emulator
net assignment problem
edge coloring
nearly equitable edge coloring
In this paper, we consider the net assignment problem in the logic emulation system. This problem is also known as the board-level-routing problem. There are field programmable logic arrays (FPGAs) and crossbars on an emulator board. Each FPGA is connected to each crossbar. Connection requests between FPGAs are called nets, and FPGAs are interconnected through crossbars. We are required to assign each net to the suitable crossbar. This problem is known to be NP-complete in general. A polynomial time algorithm is known for a certain restricted case, in which we treat only 2-terminal nets. In this paper we propose a new polynomial time algorithm for this case.
Institute of Electronics, Information and Communication Engineers
2001-05-01
eng
journal article
VoR
http://hdl.handle.net/2237/15062
https://nagoya.repo.nii.ac.jp/records/13167
http://www.ieice.org/jpn/trans_online/index.html
0916-8508
IEICE transactions on fundamentals of electronics, communications and computer sciences
E84-A
5
1161
1165
https://nagoya.repo.nii.ac.jp/record/13167/files/461.pdf
application/pdf
258.4 kB
2018-02-20