Search

Your search keyword '"Nakano, Shin-ichi"' showing total 22 results
Start Over Author "Nakano, Shin-ichi" Topic algorithm

Refine your results

more »

more »

22 results on '"Nakano, Shin-ichi"'

2. Escape from the Room

Author

Kimura, Kento, Amano, Kazuyuki, Nakano, Shin-ichi, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Zhang, Yong, editor, Miao, Dongjing, editor, and Möhring, Rolf, editor

Published
2022
Full Text
View/download PDF

3. The Coverage Problem by Aligned Disks

Author

Nakano, Shin-ichi, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Chen, Chi-Yeh, editor, Hon, Wing-Kai, editor, Hung, Ling-Ju, editor, and Lee, Chia-Wei, editor

Published
2021
Full Text
View/download PDF

4. Floorplans with Walls

Author

Yamanaka, Katsuhisa, Nakano, Shin-ichi, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Chen, Jianer, editor, Feng, Qilong, editor, and Xu, Jinhui, editor

Published
2020
Full Text
View/download PDF

5. Exact Algorithms for the Max-Min Dispersion Problem

Author

Akagi, Toshihiro, Araki, Tetsuya, Horiyama, Takashi, Nakano, Shin-ichi, Okamoto, Yoshio, Otachi, Yota, Saitoh, Toshiki, Uehara, Ryuhei, Uno, Takeaki, Wasa, Kunihiro, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Chen, Jianer, editor, and Lu, Pinyan, editor

Published
2018
Full Text
View/download PDF

6. A Simple Algorithm for r-gatherings on the Line

Author

Nakano, Shin-ichi, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Rahman, M. Sohel, editor, Sung, Wing-Kin, editor, and Uehara, Ryuhei, editor

Published
2018
Full Text
View/download PDF

7. Max-Min Dispersion on a Line

Author

Araki, Tetsuya, Nakano, Shin-ichi, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Kim, Donghyun, editor, Uma, R. N., editor, and Zelikovsky, Alexander, editor

Published
2018
Full Text
View/download PDF

8. Enumerating floorplans with walls.

Author

Yamanaka, Katsuhisa and Nakano, Shin-ichi

Subjects
*FLOOR plans, *GEOGRAPHIC boundaries, *RECTANGLES
Abstract

Let P be a set of n points in the proper inside of an axis-aligned rectangle R , and each point in P has a type, which is h-type, v-type, or f-type. Those are shortened forms of horizontal type, vertical type, and free type. We wish to dissect R into a set S of n + 1 rectangles by n horizontal or vertical line segments so that each point in P is on the common boundary line segment between two rectangles in S , and also each h-type point in P is on a horizontal line segment, each v-type point in P is on a vertical line segment, and each f-type point in P is on a horizontal or vertical line segment. Such a dissection of R is called a feasible floorplan of R with respect to P. Each point in P corresponds to the location of a structurally necessary horizontal or vertical wall, or a column (pillar) to support the upper part. In this paper, when P consists of points of the three described types, we present an efficient algorithm that enumerates all the feasible floorplans of R with respect to P. The algorithm is based on the reverse search method and enumerates all the feasible floorplans in O (n | S P |) time using O (n 2) space, after O (n log n) time preprocessing, where S P is the set of the feasible floorplans of R with respect to P. Moreover, we show that, after O (n log n) time preprocessing, one can enumerate all feasible floorplans in S P in O (n) delay using O (n 2) space. [ABSTRACT FROM AUTHOR]

Published
2024
Full Text
View/download PDF

9. Floorplans with Columns

Author

Yamanaka, Katsuhisa, Rahman, Md. Saidur, Nakano, Shin-Ichi, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Gao, Xiaofeng, editor, Du, Hongwei, editor, and Han, Meng, editor

Published
2017
Full Text
View/download PDF

10. Family Trees for Enumeration.

Author

Nakano, Shin-Ichi

Subjects
*GENEALOGY, *PLANAR graphs, *MULTICASTING (Computer networks)
Abstract

In this paper we design efficient algorithms for enumerating (1) the rooted trees with exactly n vertices, (2) the maximal planar graphs with exactly n vertices and (3) the linear extensions of a given poset. Those algorithms are based on tree structures of objects, called the family trees. The first algorithm enumerates each ordered tree with exactly n vertices in O (1) time for each after O (n) time preprocessing. The second algorithm enumerates each maximal planar graph with exactly n vertices in O (n 3) time for each on average. The third algorithm enumerates each linear extension of a given poset in O (1) time for each after O (n 2) time preprocessing, where n is the number of the element in the set of the poset. [ABSTRACT FROM AUTHOR]

Published
2023
Full Text
View/download PDF

11. On r-Gatherings on the Line

Author

Akagi, Toshihiro, Nakano, Shin-ichi, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Wang, Jianxin, editor, and Yap, Chee, editor

Published
2015
Full Text
View/download PDF

12. Efficient Enumeration of Ordered Trees with k Leaves (Extended Abstract)

Author

Yamanaka, Katsuhisa, Otachi, Yota, Nakano, Shin-ichi, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Das, Sandip, editor, and Uehara, Ryuhei, editor

Published
2009
Full Text
View/download PDF

14. The Coverage Problem by Aligned Disks.

Author

Nakano, Shin-ichi

Subjects
*DIRECTED acyclic graphs, *GRAPH algorithms, *CONSUMPTION (Economics), *DYNAMIC programming
Abstract

Given a set C of points and a horizontal line L in the plane and a set F of points on L , we want to find a set of disks such that (1) each disk has the center at a point in F (but with arbitrary radius), (2) each point in C is covered by at least one disk, and (3) the cost of the set of disks is minimized. Here the (transmission) cost of a disk with radius r is r α , where α is a positive constant depending on the power consumption model, and the cost of a set of disk is the sum of the cost of disks in the set. In this paper we first give an algorithm based on dynamic programming method to solve the problem in L 1 metric. A naive dynamic programming algorithm runs in O (| C | 3 | F | 2) time. We design an algorithm which runs in O (| C | | F | 2 + | C | log | C |) time. Then we design another algorithm to solve the problem in L 1 metric based on a reduction to a shortest path problem in a directed acyclic graph. The running time of the algorithm is O (| C | 2 + | C | | F |). [ABSTRACT FROM AUTHOR]

Published
2023
Full Text
View/download PDF

15. Box-Rectangular Drawings of Plane Graphs

Author

Rahman, Md. Saidur, Nakano, Shin-ichi, Nishizeki, Takao, Goos, Gerard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Widmayer, Peter, editor, Neyer, Gabriele, editor, and Eidenbenz, Stephan, editor

Published
1999
Full Text
View/download PDF

17. Efficient Enumeration of All Ladder Lotteries with k Bars

Author

YAMANAKA, Katsuhisa and NAKANO, Shin-ichi

Subjects
algorithm, ladder lottery, family tree, enumeration
Abstract

A ladder lottery, known as the “Amidakuji” in Japan, is a network with n vertical lines and many horizontal lines each of which connects two consecutive vertical lines. Each ladder lottery corresponds to a permutation. Ladder lotteries are frequently used as natural models in many areas. Given a permutation π, an algorithm to enumerate all ladder lotteries of π with the minimum number of horizontal lines is known. In this paper, given a permutation π and an integer k, we design an algorithm to enumerate all ladder lotteries of π with exactly k horizontal lines.

Published
2014

18. Generating all realizers.

Author

Yamanaka, Katsuhisa and Nakano, Shin-Ichi

Subjects
*ALGORITHMS, *MATHEMATICAL models, *SIMULATION methods & models, *GRAPHIC methods, *ALGEBRA
Abstract

A realizer of a triangulated plane graph G is a partition of interior edges of G, satisfying some conditions. The realizer has many applications, including graph drawing algorithms. Given a triangulated plane graph G, no algorithm to generate all realizers of G is known. In this paper, we first give an algorithm to generate all realizers. We first define a left canonical ordering for the vertices of an input graph, then show that there is a bijection between the left canonical orderings and realizers. Based on the bijection, we give an algorithm to generate all realizers. The algorithm generates each realizer in O(n) time without duplications, where n is the number of vertices in the graph. © 2006 Wiley Periodicals, Inc. Electron Comm Jpn Pt 2, 89(7): 40–47, 2006; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjb.20276 [ABSTRACT FROM AUTHOR]

Published
2006
Full Text
View/download PDF

19. Rectangular drawings of plane graphs without designated corners

Author

Rahman, Md. Saidur, Nakano, Shin-ichi, and Nishizeki, Takao

Subjects
*PLANE geometry, *GRAPHIC methods
Abstract

This paper addresses the problem of finding rectangular drawings of plane graphs, in which each vertex is drawn as a point, each edge is drawn as a horizontal or a vertical line segment, and the contour of each face is drawn as a rectangle. A graph is a 2–3 plane graph if it is a plane graph and each vertex has degree 3 except the vertices on the outer face which have degree 2 or 3. A necessary and sufficient condition for the existence of a rectangular drawing has been known only for the case where exactly four vertices of degree 2 on the outer face are designated as corners in a 2–3 plane graph G. In this paper we establish a necessary and sufficient condition for the existence of a rectangular drawing of G for the general case in which no vertices are designated as corners. We also give a linear-time algorithm to find a rectangular drawing of G if it exists. [Copyright &y& Elsevier]

Published
2002
Full Text
View/download PDF

20. Efficient enumeration of ordered trees with leaves

Author

Yamanaka, Katsuhisa, Otachi, Yota, and Nakano, Shin-ichi

Subjects
*COMBINATORIAL enumeration problems, *TREE graphs, *COMPUTER algorithms, *LEAVES, *ALGORITHMS, *COMBINATORICS
Abstract

Abstract: This paper presents a simple algorithm to generate all ordered trees with exactly vertices including exactly leaves. The best known algorithm generates such trees in time per tree, whereas our algorithm generates such trees in time per tree in the worst case. [Copyright &y& Elsevier]

Published
2012
Full Text
View/download PDF

21. Broadcasting in Heterogeneous Tree Networks with Uncertainty

Author

Tsou, Cheng-Hsiao, Chen, Gen-Huey, Lin, Ching-Chi, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Asano, Takao, editor, Nakano, Shin-ichi, editor, Okamoto, Yoshio, editor, and Watanabe, Osamu, editor

Published
2011
Full Text
View/download PDF

22. Upward Drawings of Trees on the Minimum Number of Layers : (Extended Abstract)

Author

Alam, Md. Jawaherul, Samee, Md. Abul Hassan, Rabbi, Md. Mashfiqui, Rahman, Md. Saidur, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Nakano, Shin-ichi, editor, and Rahman, Md. Saidur, editor

Published
2008
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results