624 results on '"Uehara, Ryuhei"'
Number of results to display per page
Search Results
602. Colinear Coloring on Graphs
- Author
-
Ioannidou, Kyriaki, Nikolopoulos, Stavros D., 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
603. Recursive Generation of 5-Regular Planar Graphs
- Author
-
Hasheminezhad, Mahdieh, McKay, Brendan D., Reeves, Tristan, 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
604. Maximum Neighbour Voronoi Games
- Author
-
Rasheed, Md. Muhibur, Hasan, Masud, Rahman, M. Sohel, 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
605. All Farthest Neighbors in the Presence of Highways and Obstacles
- Author
-
Bae, Sang Won, Korman, Matias, Tokuyama, Takeshi, 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
606. Foundations of Exact Rounding
- Author
-
Yap, Chee K., Yu, Jihun, 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
607. Shortest Gently Descending Paths
- Author
-
Ahmed, Mustaq, Lubiw, Anna, Maheshwari, Anil, 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
608. On Exact Solutions to the Euclidean Bottleneck Steiner Tree Problem
- Author
-
Bae, Sang Won, Lee, Chunseok, Choi, Sunghee, 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
609. Algorithms for Computing Diffuse Reflection Paths in Polygons
- Author
-
Ghosh, Subir Kumar, Goswami, Partha Pratim, Maheshwari, Anil, Nandy, Subhas Chandra, Pal, Sudebkumar Prasant, Sarvattomananda, Swami, 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
610. Approximating Shortest Paths in Graphs
- Author
-
Sen, Sandeep, 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
611. A Separator Theorem for String Graphs and Its Applications
- Author
-
Fox, Jacob, Pach, János, 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
612. Complexity of Tiling a Polygon with Trominoes or Bars.
- Author
-
Horiyama, Takashi, Ito, Takehiro, Nakatsuka, Keita, Suzuki, Akira, and Uehara, Ryuhei
- Subjects
- *
TILING (Mathematics) , *POLYOMINOES , *COMBINATORIAL designs & configurations , *TILING spaces , *APERIODIC tilings - Abstract
We study the computational hardness of the tiling puzzle with polyominoes, where a polyomino is a right-angled polygon (i.e., a polygon made by connecting unit squares along their edges). In the tiling problem, we are given a right-angled polygon P and a set S of polyominoes, and asked whether P can be covered without any overlap using translated copies of polyominoes in S. In this paper, we focus on trominoes and bars as polyominoes; a tromino is a polyomino consisting of three unit squares, and a bar is a rectangle of either height one or width one. Notice that there are essentially two shapes of trominoes, that is, I-shape (i.e., a bar) and L-shape. We consider the tiling problem when restricted to only L-shape trominoes, only I-shape trominoes, both L-shape and I-shape trominoes, or only two bars. In this paper, we prove that the tiling problem remains NP-complete even for such restricted sets of polyominoes. All reductions are carefully designed so that we can also prove the # P-completeness and ASP-completeness of the counting and the another-solution-problem variants, respectively. Our results answer two open questions proposed by Moore and Robson (Discrete Comput Geom 26:573-590, 2001) and Pak and Yang (J Comb Theory 120:1804-1816, 2013). [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
613. Common developments of three incongruent boxes of area 30.
- Author
-
Xu, Dawei, Horiyama, Takashi, Shirakawa, Toshihiro, and Uehara, Ryuhei
- Subjects
- *
POLYGONS , *GENERALIZED polygons , *HEXAGONS , *OCTAGONS , *QUADRILATERALS - Abstract
We investigate common developments that can fold into plural incongruent orthogonal boxes. Recently, it was shown that there are infinitely many orthogonal polygons that fold into three boxes of different size. However, the smallest one that folds into three boxes consists of 532 unit squares. From the necessary condition, the smallest possible surface area that can fold into two boxes is 22, and the smallest possible surface area for three different boxes is 46. For the area 22, it has been shown that there are 2,263 common developments of two boxes by exhaustive search. However, the area 46 is too huge to search. In this paper, we focus on the polygons of area 30, which is the second smallest area of two boxes that admits to fold into two boxes of size 1 × 1 × 7 and 1 × 3 × 3 . Moreover, when we fold along diagonal lines of rectangles of size 1 × 2 , this area 30 may admit to fold into a box of size 5 × 5 × 5 . The results are summarized as follows. There exist 1,080 common developments of two boxes of size 1 × 1 × 7 and 1 × 3 × 3 . Among them, there are nine common developments of three boxes of size 1 × 1 × 7 , 1 × 3 × 3 , and 5 × 5 × 5 . Interestingly, one of nine such polygons folds into three different boxes 1 × 1 × 7 , 1 × 3 × 3 , and 5 × 5 × 5 in four different ways. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
614. Ferrers dimension of grid intersection graphs.
- Author
-
Chaplick, Steven, Hell, Pavol, Otachi, Yota, Saitoh, Toshiki, and Uehara, Ryuhei
- Subjects
- *
INTERSECTION graph theory , *BIPARTITE graphs , *PERMUTATIONS , *MATHEMATICAL analysis , *APPLIED mathematics - Abstract
We investigate the Ferrers dimension of classes of grid intersection graphs and show properties and characterizations. In particular, we show that (1) the grid intersection graphs form a proper subclass of the class of bipartite graphs of Ferrers dimension 4, (2) segment-ray graphs have a forbidden submatrix characterization, and (3) a bipartite graph is a unit grid intersection graph if and only if it is the intersection of two bipartite permutation graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
615. Line Transversals and Pinning Numbers
- Author
-
Cheong, Otfried, 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
616. Competitive Location Problems: Balanced Facility Location and the One-Round Manhattan Voronoi Game
- Author
-
Sándor P. Fekete, Jörg Kalcsics, Thomas Byrne, Linda Kleist, Uehara, Ryuhei, Hong, Seok-Hee, and Nandy, Subhas C.
- Subjects
QA75 ,Computer Science::Computer Science and Game Theory ,021103 operations research ,0211 other engineering and technologies ,0102 computer and information sciences ,02 engineering and technology ,Characterization (mathematics) ,01 natural sciences ,Facility location problem ,Domain (mathematical analysis) ,Combinatorics ,010201 computation theory & mathematics ,Euclidean geometry ,Metric (mathematics) ,Voronoi diagram ,Mathematics - Abstract
We study competitive location problems in a continuous setting, in which facilities have to be placed in a rectangular domain R of normalized dimensions of 1 and \(\rho \ge 1\), and distances are measured according to the Manhattan metric. We show that the family of balanced configurations (in which the Voronoi cells of individual facilities are equalized with respect to geometric properties) is richer in this metric than for Euclidean distances. Our main result considers the One-Round Voronoi Game with Manhattan distances, in which first player White and then player Black each place n points in R; each player scores the area for which one of its facilities is closer than the facilities of the opponent. We give a tight characterization: White has a winning strategy if and only if \(\rho \ge n\); for all other cases, we present a winning strategy for Black.
- Published
- 2021
617. Efficient segment folding is hard.
- Author
-
Horiyama, Takashi, Klute, Fabian, Korman, Matias, Parada, Irene, Uehara, Ryuhei, and Yamanaka, Katsuhisa
- Subjects
- *
ORIGAMI , *NP-hard problems - Abstract
We introduce a computational origami problem which we call the segment folding problem: given a set of n line-segments in the plane the aim is to make creases along all segments in the minimum number of folding steps. Note that a folding might alter the relative position between the segments, and a segment could split into two. We show that it is NP-hard to determine whether n line segments can be folded in n simple folding operations. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
618. Ununfoldable polyhedra with 6 vertices or 6 faces.
- Author
-
Akitaya, Hugo A., Demaine, Erik D., Eppstein, David, Tachi, Tomohiro, and Uehara, Ryuhei
- Subjects
- *
EDGES (Geometry) , *ORIGAMI , *POLYHEDRA - Abstract
We update the record of the simplest possible topologically convex polyhedron that has no edge unfolding, measuring complexity in terms of number of vertices or number of faces. Specifically, we prove that 6 vertices are sufficient, and that 6 faces are sufficient, for ununfoldability. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
619. UNO is hard, even for a single player.
- Author
-
Demaine, Erik D., Demaine, Martin L., Harvey, Nicholas J.A., Uehara, Ryuhei, Uno, Takeaki, and Uno, Yushi
- Subjects
- *
CARD games , *COMPUTER algorithms , *COMBINATORIAL games , *GAME theory , *COMPUTATIONAL complexity , *MATHEMATICAL proofs - Abstract
Abstract: This paper investigates the popular card game UNO® from the viewpoint of algorithmic combinatorial game theory. We define simple and concise mathematical models for the game, including both cooperative and uncooperative versions, and analyze their computational complexity. In particular, we prove that even a single-player version of UNO is NP-complete, although some restricted cases are in P. Surprisingly, we show that the uncooperative two-player version is also in P. [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
620. An Open Pouring Problem
- Author
-
Frei, Fabian, Rossmanith, Peter, Wehner, David, Farach-Colton, Martin, Prencipe, Giuseppe, and Uehara, Ryuhei
- Subjects
Water Jug Riddle ,Pitcher Pouring Problem ,Water Bucket Problem ,Vessel Puzzle ,Complexity ,Die Hard ,Theory of computation → Representations of games and their complexity ,Theory of computation → Theory and algorithms for application domains - Abstract
We analyze a little riddle that has challenged mathematicians for half a century. Imagine three clubs catering to people with some niche interest. Everyone willing to join a club has done so and nobody new will pick up this eccentric hobby for the foreseeable future, thus the mutually exclusive clubs compete for a common constituency. Members are highly invested in their chosen club; only a targeted campaign plus prolonged personal persuasion can convince them to consider switching. Even then, they will never be enticed into a bigger group as they naturally pride themselves in avoiding the mainstream. Therefore each club occasionally starts a campaign against a larger competitor and sends its own members out on a recommendation program. Each will win one person over; the small club can thus effectively double its own numbers at the larger one’s expense. Is there always a risk for one club to wind up with zero members, forcing it out of business? If so, how many campaign cycles will this take?, Leibniz International Proceedings in Informatics (LIPIcs), 157, ISSN:1868-8969, 10th International Conference on Fun with Algorithms (FUN 2021), ISBN:978-3-95977-145-0
- Published
- 2020
- Full Text
- View/download PDF
621. Collaborative Procrastination
- Author
-
Anagnostopoulos, Aris, Gionis, Aristides, Parotsidis, Nikos, Farach-Colton, Martin, Prencipe, Giuseppe, Uehara, Ryuhei, Martin Farach-Colton, Giuseppe Prencipe, and Ryuhei Uehara
- Subjects
Applied computing → Sociology ,collaborative environments ,Computational behavioral science ,Collaborative environments ,Collaborative work ,Time-inconsistent planning ,collaborative work ,time-inconsistent planning, computational behavioral science, collaborative work, collaborative environments ,time-inconsistent planning ,computational behavioral science ,Applied computing → Economics - Abstract
The problem of inconsistent planning in decision making, which leads to undesirable effects such as procrastination, has been studied in the behavioral-economics literature, and more recently in the context of computational behavioral models. Individuals, however, do not function in isolation, and successful projects most often rely on team work. Team performance does not depend only on the skills of the individual team members, but also on other collective factors, such as team spirit and cohesion. It is not an uncommon situation (for instance, experienced by the authors while working on this paper) that a hard-working individual has the capacity to give a good example to her team-mates and motivate them to work harder. In this paper we adopt the model of Kleinberg and Oren (EC'14) on time-inconsistent planning, and extend it to account for the influence of procrastination within the members of a team. Our first contribution is to model collaborative work so that the relative progress of the team members, with respect to their respective subtasks, motivates (or discourages) them to work harder. We compare the total cost of completing a team project when the team members communicate with each other about their progress, with the corresponding cost when they work in isolation. Our main result is a tight bound on the ratio of these two costs, under mild assumptions. We also show that communication can either increase or decrease the total cost. We also consider the problem of assigning subtasks to team members, with the objective of minimizing the negative effects of collaborative procrastination. We show that whereas a simple problem of forming teams of two members can be solved in polynomial time, the problem of assigning n tasks to n agents is NP-hard.
- Published
- 2020
- Full Text
- View/download PDF
622. Symmetric assembly puzzles are hard, beyond a few pieces.
- Author
-
Demaine, Erik D., Korman, Matias, Ku, Jason S., Mitchell, Joseph S.B., Otachi, Yota, van Renssen, André, Roeloffzen, Marcel, Uehara, Ryuhei, and Uno, Yushi
- Subjects
- *
PUZZLES , *POLYNOMIAL time algorithms , *INTERIOR-point methods , *INTERIOR architecture - Abstract
We study the complexity of symmetric assembly puzzles: given a collection of simple polygons, can we translate, rotate, and possibly flip them so that their interior-disjoint union is line symmetric? On the negative side, we show that the problem is strongly NP-complete even if the pieces are all polyominos. On the positive side, we show that the problem can be solved in polynomial time if the number of pieces is a fixed constant. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
623. Folding Augmented: A Design Method for Structural Folding in Architecture
- Author
-
D'Acunto, Pierluigi, Castellón González, Juan José, Kawasaki, Toshikazu, Uehara, Ryuhei, Tachi, Tomohiro, and Maekawa, Jun
- Abstract
The 6th Interntaional Meeting on Origami in Science, Mathematics and Education : Program and Abstracts : held at The University of Tokyo, August 10-13, 2014
- Published
- 2014
- Full Text
- View/download PDF
624. The Voronoi game on graphs and its complexity
- Author
-
Sachio Teramoto, Ryuhei Uehara, Erik D. Demaine, Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science, Demaine, Erik D., and Uehara, Ryuhei
- Subjects
Discrete mathematics ,graph algorithms ,Computer Science::Computer Science and Game Theory ,Theoretical computer science ,General Computer Science ,ComputingMilieux_PERSONALCOMPUTING ,Game complexity ,Computer Science Applications ,Theoretical Computer Science ,NP-completeness ,Computational Theory and Mathematics ,Voronoi Game ,Geometry and Topology ,Graph algorithms ,Voronoi diagram ,Mathematics ,PSPACE-completeness - Abstract
The Voronoi game is a two-person game which is a model for a competitive facility location. The game is played on a continuous domain, and only two special cases (one-dimensional case and one-round case) are well investigated. We introduce the discrete Voronoi game in which the game arena is given as a graph. We first analyze the game when the arena is a large complete k-ary tree, and give an optimal strategy. When both players play optimally, the first player wins when k is odd, and the game ends in a tie for even k. Next we show that the discrete Voronoi game is intractable in general. Even for the one-round case in which the strategy adopted by the first player consist of a fixed single node, deciding whether the second player can win is NP-complete. We also show that deciding whether the second player can win is PSPACE-complete in general.
- Published
- 2011
Catalog
Books, media, physical & digital resources
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.