On the Complexity of Reconfiguration Problems (2009)
Takehiro Ito, Erik D. Demaine, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, ...
Abstract. Reconfiguration problems arise when we wish to find a stepby-step transformation between two feasible solutions of a problem such that all intermediate results are also feasible. We...
Computational Complexity of a Pop-up Book ∗ (2008)
Ryuhei Uehara, Sachio Teramoto
Origami is the centuries-old art of folding paper, and recently, it is investigated as computer science: Given an origami with creases, the problem to determine if it can be flat after folding all...
Linear Structure of Bipartite Permutation Graphs and the Longest Path Problem (2008)
Ryuhei Uehara, Gabriel Valiente
The class of bipartite permutation graphs is the intersection of two well known graph classes: bipartite graphs and permutation graphs. A complete bipartite decomposition of a bipartite permutation...
Linear-Time Counting Algorithms for Independent Sets in Chordal Graphs (2008)
Yoshio Okamoto, Takeaki Uno, Ryuhei Uehara
We study some counting and enumeration problems for chordal graphs, especially concerning independent sets. We first provide the following efficient algorithms for a chordal graph: (1) a linear-time...
Tree Spanners for Bipartite Graphs and Probe Interval Graphs 1 (2008)
Andreas Br, Feodor F. Dragan, Hoang-oanh Le, Van Bang Le, Ryuhei Uehara
Abstract. A tree t-spanner T in a graph G is a spanning tree of G such that the distance between every pair of vertices in T is at most t times their distance in G. The tree t-spanner problem asks...
Tree Spanners for Bipartite Graphs and Probe Interval Graphs 1 (2008)
Andreas Br, Feodor F. Dragan, Hoang-oanh Le, Van Bang Le, Ryuhei Uehara
Abstract. A tree t-spanner T in a graph G is a spanning tree of G such that the distance between every pair of vertices in T is at most t times their distance in G. The tree t-spanner problem asks...
Mathematical and Computing Sciences (2008)
Naoto Miyoshi, Takeya Shigezumi, Ryuhei Uehara, Osamu Watanabe
Scale free graphs have attracted attention by their non-uniform structure that can be used as a model for various social and physical networks. In this paper, we propose two natural and simple random...
immigration-death processes (2008)
Naoto Miyoshi, Mariko Ogura, Takeya Shigezumi, Ryuhei Uehara, Naoto Miyoshi, Mariko Ogura, ...
Scale-free graphs have recently attracted much attention since so-called scale-free phenomena have really appeared in various physical and social networks, where a graph is said to be scale-free if...
Longest Path Problems on Ptolemaic Graphs (2008)
TAKAHARA, Yoshihiro, TERAMOTO, Sachio, UEHARA, Ryuhei
Longest path problem is a problem for finding a longest path in a given graph. While the graph classes in which the Hamiltonian path problem can be solved efficiently are widely investigated, there...
Fast Parallel Approximation Algorithms for Maximum Weighted Matching Problem (2007)
We present two parallel approximation algorithms for finding a matching of maximum weight in a given edge-weighted graph. To deal with unbounded weights efficiently on a PRAM, the algorithms only use...
The Number of Connected Components in Graphs and Its Applications (2007)
For any given graph and an integer k, the number of connected components with k vertices in the graph is investigated. For the vertex set of size n and the maximum degree 1, the number is bounded...
Unique Solution Instance Generation for the 3-Satisfiability (3SAT) Problem (2007)
. For the 3-Satisability Problem (3SAT), we propose three algorithms for generating its positive instance (and its solution) randomly. We design these algorithms so that they produce, with high...
A New Proof for the Monte Carlo Constructibility of log log n (2007)
The Monte Carlo constructibility of log log n has proved by Karpinski and Verbeek ([KV87]). They proposed an algorithm, and proved the constructibility by applying a statistical result in [Fel57] to...
Complexity Classes Characterized by Semi-Random Sources (2007)
: The complexity classes PP; BPP and RP are usually defined via probabilistic Turing machines (PTMs) that have access to a perfect random source. A natural question is this: Do these classes change...
Partial Gates and the Identification of their Solution Sets (2007)
Ryuhei Uehara, Kensei Tsuchida
A partial gate computes a function of part of the inputs to a circuit. Some of the inputs are connected to the partial gate, and the others are not connected anywhere. For a given partial OR, AND,...
We investigate structural parameters of a graph that express the boundary of the parallel complexity of the lexicographically first maximal independent set (LFMIS) problem. The longest directed path...
Therese Biedl, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Paul Nijjar, Ryuhei Uehara, ...
We prove that there is a polyhedron with genus 6 whose faces are orthogonal polygons (equivalently, rectangles) and yet the angles between some faces are not multiples of 90, so the polyhedron itself...
Tractable and Intractable Problems on Generalized Chordal Graphs 3 (2007)
A generalized chordal graph is characterized by some positive integer k 3, and whose each cycle of length greater than k has a chord. Several tractable and intractable problems on a k-chordal graph...
Andreas Brandstadt, Feodor F. Dragan, Hoang-oanh Le, Van Bang Le, Ryuhei Uehara
Abstract. A tree t-spanner T in a graph G is a spanning tree of G such that the distance between every pair of vertices in T is at most t times their distance in G. The tree t-spanner problem asks...
Canonical tree representation of distance hereditary graphs and its applications (2006)
The class of distance hereditary graphs consists of the isometric graphs. That is, for each pair of vertices, its distance is invariant for any induced path in a distance hereditary graph. In the...
Voronoi game on graphs and its complexity (2006)
Sachio Teramoto, Erik Demaine, Ryuhei Uehara
Abstract. The Voronoi game is a two-person game which is a model for a competitive facility location. The game is done on a continuous domain, and only two special cases (1-dimensional case and...
Efficient Algorithms for Airline Problem (2006)
Shin-ichi Nakano, Ryuhei Uehara, Takeaki Uno
It is known that the airlines in the real world form small-world network. This fact implies that they are constructed with an ad hoc strategy. The small-world network is good from the viewpoint of...
On Computing Longest Paths in Small Graph Classes (2005)
The longest path problem is to find a longest path in a given graph. While the graph classes in which the Hamiltonian path problem can be solved efficiently are widely investigated, few graph classes...
Laminar Structure of Ptolemaic Graphs and Its Applications (2005)
Ptolemaic graphs are graphs that satisfy the Ptolemaic inequality for any four vertices. The graph class coincides with the intersection of chordal graphs and distance hereditary graphs. The graph...
On the Laminar Structure of Ptolemaic and Distance Hereditary Graphs (2005)
Ptolemaic graphs are graphs that satisfy ptolemaic inequality for any four vertices. The graph class coincides with the intersection of chordal graphs and distance hereditary graphs. The graph class...
A double classification tree search algorithm for index SNP selection (2004)
Zhang, Peisen, Sheng, Huitao, Uehara, Ryuhei
Abstract Background In population-based studies, it is generally recognized that single nucleotide polymorphism (SNP) markers are not independent. Rather, they are carried by haplotypes, groups of...
Canonical Data Structure for Interval Probe Graphs (2004)
The class of interval probe graphs is introduced to deal with the physical mapping and sequencing of DNA as a generalization of interval graphs. The polynomial time recognition algorithms for the...
Canonical Data Structure for Probe Interval Graphs (2004)
The class of probe interval graphs is introduced to deal with the physical mapping and sequencing of DNA as a generalization of interval graphs. The polynomial time recognition algorithms for the...
Tighter bounds on the genus of nonorthogonal polyhedra built from rectangles (2002)
Therese Biedl, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Paul Nijjar, Ryuhei Uehara, ...
Parallel Approximation Algorithms for Maximum Weighted Matching in General Graphs (2000)
. The problem of computing a matching of maximum weight in a given edge-weighted graph is not known to be P-hard or in RNC. This paper presents four parallel approximation algorithms for this...
A Measure For The Lexicographically First Maximal Independent Set Problem and Its Limits (1999)
We introduce a structural parameter of a graph, the longest directed path length (LDPL), and express the boundary of the difficulty of the problems along this parameter. The parallel complexity of...
Identification of Partial Disjunction, Parity, and Threshold Functions (1999)
Ryuhei Uehara, Kensei Tsuchida, Ingo Wegener
Let F be a class of functions obtained by replacing some inputs of a Boolean function of a fixed type with some constants. The problem considered in this paper, which is called attribute efficient...
Unique Solution Instance Generation for the 3-Satisfiability (3SAT) Problem (1999)
For the 3-Satisability Problem (3SAT), we consider a problem of generating its positive instance (and its solution) randomly. For the problem, it is desirable if an instance generation algorithm...
Probabilistic Algorithms and Complexity Classes (1998)
The main theme in this dissertation is a computation on a probabilistic Turing machine (PTM), which is a Turing machine with distinguished states called coin-tossing states. In general, it is assumed...
A Measure of Parallelization for the Lexicographically First Maximal Subgraph Problem (1997)
A maximum directed tree size (MDTS) is defined by the maximum number of the vertices of a directed tree on the directed acyclic graph of a given undirected graph. The MDTS of a graph measures the...
Collapse of PP with a Semi-Random Source to BPP (1997)
this paper. Compared with a best tree, the structure of a worst tree has many variations. The complete characterization of a worst tree remains an open problem. 2 Preliminaries
A Measure of Parallelization for the Lexicographically First Maximal Subgraph Problems (1997)
. A maximum directed tree size (MDTS) is defined by the maximum number of the vertices of a directed tree on the directed acyclic graph of a given undirected graph. The MDTS of a graph measures the...
Longest directed path length (LDPL) is defined by the length of the longest path of the directed acyclic graph of a given undirected graph. The LDPL of a graph measures the parallelization for the...
Optimal Attribute-Efficient Learning Of Disjunction, Parity, And Threshold Functions (1997)
Ryuhei Uehara, Kensei Tsuchida, Ingo Wegener
Decision trees are a very general computation model. Here the problem is to identify a Boolean function f out of a given set of Boolean functions F by asking for the value of f at adaptively chosen...
Parallel Algorithms for Maximal Linear Forests (1997)
. The maximal linear forest problem is to find, given a graph G = (V; E), a maximal subset of V that induces a linear forest. Three parallel algorithms for this problem are presented. The first one...
Fast RNC and NC Algorithms for Finding a Maximal Set of Paths with an Application (1996)
Ryuhei Uehara, Zhi-zhong Chen, Xin He
: We present two parallel algorithms for finding a maximal set of paths in a given undirected graph. The former runs in O(log n) expected time with O(n + m) processors on a CRCW PRAM. The latter runs...
Complexity Classes Characterized by Semi-Random Sources (1995)
The complexity classes characterized by semirandom sources were investigated. U.V. Vazirani and V.V Vazirani [VV85] showed that 8 ffi-RP = RP, and U.V. Vazirani [Vaz86] showed that 8 ffi-BPP = BPP,...
Efficient Simulations by a Biased Coin (1995)
this paper, bias is a rational number between 0 and