Language：Japanese   Publishing type：Research paper (scientific journal)   Publisher：The Institute of Electronics, Information and Communication Engineers  

CiNii Article

CiNii Books

researchmap

Language：English   Publishing type：Research paper (other academic)   Publisher：情報処理学会  

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

researchmap

Language：Japanese   Publishing type：Research paper (other academic)  

researchmap

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG  

A subdivision of a rectangle into rectangular faces with horizontal and vertical line segments is called a rectangular drawing or floorplan. It has been an open problem to determine whether there exist a polynomial time algorithm for computing R(n). We affirmatively solve the problem, that is, we introduce an O(n(4))-time and O(n(3))-space algorithm for R(n). The algorithm is based on a recurrence for R(n), which is the main result of the paper. We also implement our algorithm and computed R(n) for n <= 3000.

DOI： 10.1587/transfun.E92.A.1115

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

A subdivision of a rectangle into rectangular faces with horizontal and vertical line segments is called a rectangular drawing or floorplan. Yamanaka and Nakano published a (5n - 5)-bit representation of a rectangular drawing, where n is the number of inner rectangles. In this paper, a (4n-4)-bit representation of rectangular drawing is introduced. Moreover, this representation gives all alternative proof that the number of rectangles with n rectangles R(n) <= 13.5(n-1).

DOI： 10.1007/978-3-642-02882-3_6

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：IEEE  

A subdivision of a rectangle into rectangular faces with horizontal and vertical line segments is called rectangular drawings or floorplans. It is known that the number of rectangular drawings R(n) is asymptotically approximated by a geometric progression, where n is the number of inner rectangles. More precisely, there exists a constant c = lim(n ->infinity) R(n)(1/)n. The best upper and lower bounds of c ever known are 25 and 11.56, respectively. In this report, R(n) <= 13.5(n-1) is shown, which implies c <= 13.5.

DOI： 10.1109/ISCAS.2009.5117891

Web of Science

researchmap

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

CiNii Article

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG  

A floorplan is a subdivision of a rectangle into rectangular faces with horizontal and vertical line segments. We call a floorplan room-to-room when adjacencies between rooms are considered. Fujimaki and Takahashi showed that any room-to-room floorplan can be represented as a permutation. In this paper, we give an O(n)-time algorithm that constructs the vertical and the horizontal constraint graphs of a floorplan for a given permutation under this representation.

DOI： 10.1093/ietfec/e91-a.4.1071

Web of Science

researchmap

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG  

A floorplan is a subdivision of a rectangle into rectangular faces with horizontal and vertical line segments. Heuristic search algorithms are used to find desired floorplans in applications, including sheet-cutting, scheduling, and VLSI layout design. Representation of floorplan is critical in floorplan algorithms, because it determines the solution space searched by floorplan algorithms. In this paper, we show a surjective mapping from permutations to room-to-room floorplans. This mapping gives us a simple representation of room-to-room floorplans.

DOI： 10.1093/ietfec/e90-a.4.823

Web of Science

researchmap

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

CiNii Article

researchmap

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

CiNii Article

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

CiNii Article

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC  

We present an ordered tree (O tree) structure to represent nonslicing floorplans, The O tree uses only n(2 + inverted right perpendicular lg n inverted left perpendicular) bits for a floorplan of n, rectangular blocks. We define an admissible placement as a compacted placement in both a: and y directions. For each admissible placement, we can find an O-tree representation. We show that the number of possible O-tree combinations is O(n!2(2n-2)/n(1.5)). This is very concise compared to a sequence pair representation that has O((n!)(2)) combinations. The approximate ratio of sequence pair and O-tree combinations is O(n(2)(n/4e)(n)), The complexity of O tree is even smaller than a binary tree structure for slicing floorplan that has O(n!2(5n-3)/n(1.5)) combinations, Given an O tree, it takes only linear time to construct the placement and its constraint graph, We have developed a deterministic floorplanning algorithm utilizing the structure of O tree. Empirical results on MCNC (www.mcnc.org) benchmarks show promising performance with average 16% improvement in wire length and 1% less dead space over previous central processing unit (CPU) intensive cluster refinement method.

DOI： 10.1109/43.908471

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：IEEE  

In the rectangle packing problem, encoding schemes to represent the placements of rectangles are the key factors determining the efficiency of algorithms. SEQ-PAIR is one of the most sophisticated encoding scheme, which has been considered to have a small solution space [2]. In this paper, we begin with a packing procedure that does not look so smart. This procedure, however, leads us to another encoding scheme DS (the abbreviation for Dropping Schedule) whose solution space has the same size as that of SEQ-PAIR. Moreover, we introduce encoding scheme LOT as an adv ancedversion of DS, which has a smaller solution space.

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

In the rectangle packing problem, encoding schemes to represent the placements of rectangles are the key factors of efficient algorithms. In 1995, an epoch-making encoding scheme, known as SEQ-PAIR, was developed[2]. The solution space of SEQ-PAIR has been considered sufficiently small. In this paper, however, we present a simple and natural encoding scheme of rectangle packings whose solution space is smaller than that of SEQ-PAIR. © 2000 IEEE.

DOI： 10.1145/368434.368599

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：IEEE  

An L-shaped routing of a two-terminal net is its upper- or lower routing. Given a set of nets, the planar testability problem (PTP) is to decide if there exist a planar (i.e., pairwise non-crossing) L-shaped rotuing of all nets. PTP was solved via transformation to 2-satisfiability. Here, we propose an efficient greedy algorithm running in O(n(logn)(2), where n is the number of nets. The density-1 testability problem (D1TP) is to decide if there exists an L-shaped routing of all nets with density 1 (i.e., overlap routing is not allowed: however; routed may intersect each other). We extend-the PTP algorithm to solve the D1TP problem in O(nlogn) time.

Web of Science

researchmap

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG  

In mobile communication systems using Dynamic Channel Assignment, channels are possible to be rearranged so that blocking probability can be made low. The smaller the number of cells where channels are rearranged, the smaller the load on the base stations in the cells. Also, we can reduce the deterioration of communication quality caused by reassingning a new channel to a call instead of the channel already assigned. In this paper, we consider not only how to rearrange channels but also which channel should be rearranged and assigned to a new call in rearrangement, and propose very simple but effective methods for rearrangement. The ways to select a candidate channel to be rearranged and assigned to a new call in the new methods make the number of cells where a channel is rearranged smaller. We also examine the relations between characteristics and the number of cells where a channel is rearranged. Using computer simulation results, the properties of the new rearrangement methods are compared with those of the traditional methods.

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)  

researchmap

Language：Japanese   Publishing type：Doctoral thesis  

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)   Publisher：電子情報通信学会基礎・境界ソサイエティ  

CiNii Article

CiNii Books

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：I E E E  

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：Japanese   Publisher：The Institute of Electronics, Information and Communication Engineers  

For VLSI layout design, many floorplan representations have been proposed since the mid-1990s. Especially representations of box partitions (rectangular solid dissections) have studied since the 2000s. Ohta et al. proposed O-sequence which represents a box partitioned by rectangles.In this report, an alternative representation of a box partitioned by rectangles is introduced. The size of solution space of the representation is 24^<n-1>, which is an upper bound for the number of box partitions by n-1 rectangles.

CiNii Article

CiNii Books

researchmap

Language：Japanese   Publisher：The Institute of Electronics, Information and Communication Engineers  

A rectangular partition is a subdivision of a rectangle into rectangles by horizontal and vertical line segments. Enumerating the number of rectangular partitions into n rectangles is an interesting combinatorial problem. Recently, it has been proved that there exists a bijection between rectangular partitions and Baxter permutations. That is, the problem is reduced to enumeration of the number of Baxter permutations. However, all known formulae and recurrences are complicated. In this report, we derive a simple linear recurrence and an enumerating algorithm directly from rectangular partitions.

CiNii Article

CiNii Books

researchmap

Language：Japanese   Publisher：The Institute of Electronics, Information and Communication Engineers  

CiNii Article

CiNii Books

researchmap

Language：Japanese   Publisher：The Institute of Electronics, Information and Communication Engineers  

For a given set S of n points on the xy-plane, including the origin, a rectilinear Steiner arborescence (RSA) is a rooted tree such that every path from the origin to the points in S is the shortest path consisting of horizontal and vertical line segments. An RSA of minimum total length of line segments is called a minimum RSA (MRS A). Cong and Leung proposed a fast exact algorithm RS A/DP to find an MRS A if all points in S are in the first quadrant. We introduced a new pruning rule to revise RSA/DP. The computational experiment showed that for n = 100, the number of subproblems generated by RSA/DP+ is 1/100 of that of RSA/DP. In this report, we propose an additional pruning rule and introduce a new algorithm RSA/DP++. The computational experiment shows that the number of subproblems generated by RSA/DP++ is less than half of that of RSA/DP+ and the computational time and the size of tractable instances are improved.

CiNii Article

CiNii Books

researchmap

Language：Japanese  

CiNii Article

researchmap

Language：Japanese   Publisher：The Institute of Electronics, Information and Communication Engineers  

For a given set S of n points on the xy-plane, including the origin, a rectilinear Steiner arborescence (RSA) is a rooted tree such that every path from the origin to the points in S is the shortest path consisting of horizontal and vertical line segments. An RSA of minimum total length of line segments is called a Minimum RSA (MRSA). Cong and Leung proposed a fast exact algorithm RSA/DP to find a MRSA if all points in S are in the first quadrant. In this report, we propose a new pruning rule to accelerate RSA/DP. The experiment results show the effectiveness of the rule.

CiNii Article

CiNii Books

researchmap

Language：Japanese   Publisher：The Institute of Electronics, Information and Communication Engineers  

Ford-Fulkerson's labeling method is a classic algorithm for maximum network flows. The labeling method always terminates on networks with integral (rational) capacities. On the other hand, it might fail to terminate if networks have an edge of an irrational capacity. All the examples of such networks ever published have some special irrational edge capacities. In this report, we introduce the simplest and smallest example with an edge of arbitrary irrational capacity. This example suggests that many networks with real-valued edge capacities have infinite sequences of flow augmentations.

CiNii Article

CiNii Books

researchmap

Language：Japanese   Publisher：The Institute of Electronics, Information and Communication Engineers  

CiNii Article

CiNii Books

researchmap

Language：Japanese   Publisher：The Institute of Electronics, Information and Communication Engineers  

CiNii Article

CiNii Books

researchmap

Language：Japanese   Publisher：The Institute of Electronics, Information and Communication Engineers  

In this report, we introduce a representation of stacked rectangular drawings. This representation is a proper extension of FT Squeeze, which is a representation of a single rectangular drawings.

CiNii Article

CiNii Books

researchmap

Language：Japanese   Publisher：The Institute of Electronics, Information and Communication Engineers  

CiNii Article

CiNii Books

researchmap

Language：Japanese   Publisher：The Institute of Electronics, Information and Communication Engineers  

CiNii Article

CiNii Books

researchmap

Language：English   Publishing type：Article, review, commentary, editorial, etc. (other)   Publisher：IEEE Circuits and Systems Society  

We present an ordered tree (O-tree) structure to represent nonslicing floorplans. The O-tree uses only n (2 + [lg n]) bits for a floorplan of n rectangular blocks. We define an admissible placement as a compacted placement in both X and y directions. For each admissible placement, we can find an O-tree representation. We show that the number of possible O-tree combinations is 0(n!2 2n-2/n 1.5). This is very concise compared to a sequence pair representation that has O((n!) 2) combina-tions. The approximate ratio of sequence pair and O-tree combinations is O(n 2(n/4e) n). The complexity of an O-tree is even smaller than a binary tree structure for a slicing floorplan that has O(n!2 5n-3/n 1.5) combinations. Given an O-tree, it takes only linear time to construct the placement and its constraint graph. We have developed a deterministic floorplanning algorithm utilizing the structure of O-tree. Empirical results on MCNC (www.mcnc.org) benchmarks show promising performance with average 16% improvement in wire length and 1% less dead space over the previous central processing unit (CPU) intensive cluster refinement method.

DOI： 10.1109/MCAS.2003.1242834

Scopus

researchmap

Language：Japanese   Publisher：The Institute of Electronics, Information and Communication Engineers  

H. Murata, K. Fbjiyoshi, S. Nakatake, and Y. Kajitani introduced a epoch-making coding scheme for feasible solutions of rectangle packing problem. This scheme is called SEQ-PAIR and highly improved the computational time. We present an algorithm for finding a maximum-weight decreasing sequence in a permutation and show its effectivity for the rectangle packing algorithm.The time complexity of the algorithm presented in this report is O(nω), where ω is the weight of the maximum weight decreasing sequence. However, we can get O(n log n)-time algorithm on adopting balanced tree for its data structure. This algorithm is also the fastest one for finding maximum weighted clique in a weighted permutation graph.

CiNii Article

CiNii Books

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

Venue：別府国際コンベンションセンター  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Poster presentation  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (invited, special)  

Venue：北九州市立大学  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：愛媛大学  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap