Results 1 - 20 of about 38 for Ryuhei Uehara. (0.39 seconds)
Copyright by
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 class can also be seen as a natural generalization of block graphs (and hence trees). In this paper, a new characterization of ptolemaic graphs is presented. It is a laminar structure of cliques, and leads us to a canonical tree representation. The tree representation gives a simple intersection model for ptolemaic graphs. The tree representation is constructed in linear time from a perfect elimination ordering obtained by the lexicographic breadth first search. Hence the recognition and the graph isomorphism for ptolemaic graphs can be solved in linear time. Using the tree representation, we also give an O(n) time algorithm for the Hamiltonian cycle problem. The Hamiltonian cycle problem is NP-hard for chordal graphs, and an O(n + m) time algorithm is known for distance hereditary graphs.
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 paper, a canonical tree representation of a distance hereditary graph is proposed. A linear time algorithm for computing the tree representation is also presented. Hence the recognition problem and the graph isomorphism problem for the graph class can be solved in linear time, thanks to linear time isomorphism algorithm for labeled trees. The tree representation takes O(|V |) space for a distance hereditary graph G = (V, E). Hence it can be used as a compact data structure for the graph. It is so informative that all pruning sequences, which is a previously known characterization based on a vertex ordering, can be generated from the tree representation efficiently.
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 creases is NP-hard. Another hundreds-old art of folding paper is a pop-up book. A model for the pop-up book design problem is given, and its computational complexity is investigated. We show that both of the opening book problem and the closing book problem are NP-hard. Keywords: Computational Complexity, Origami, Paper folding, Pop-up book. 1
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 are known to be solved efficiently for the longest path problem. For a tree, a simple linear time algorithm for the longest path problem is known. We first generalize the algorithm, and show that the longest path problem can be solved efficiently for weighted trees, block graphs, and cacti. We next show that the longest path problem can be solved efficiently on some graph classes that have natural interval representations.
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 graph class are known. However, the complexity of the graph isomorphism problem for the class is still unknown. In this paper, extended MPQ-trees are proposed to represent the probe interval graphs. An extended MPQtree is canonical and represents all possible permutations of the intervals. The extended MPQ-tree can be constructed from a given probe interval graph in O(n 2 + m) time. Thus we can solve the graph isomorphism problem for the probe interval graphs in O(n 2 + m) time. Using the tree, we can determine that any two nonprobes are independent, overlapping, or their relation cannot be determined without an experiment. Therefore, we can heuristically find the best nonprobe that would be probed in the next experiment. Also, we can enumerate all possible affirmative interval graphs for given probe interval graph.
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 customers; they can fly to any destination through a few airline hubs. However, it is not the best solution for the managers. In this paper, we assume that customers are silent and they never complain. This assumption is appropriate for transportation service, and some network design. Under this assumption, the airline problem is to construct the least cost connected network for given distribution of the populations of cities (with no a priori connection). First, we show an efficient algorithm that produces a good network from the viewpoint of the managers; the algorithms minimizes the number of vacant seats. The resultant network contains at most n connections (or edges), where n is the number of cities. Next we aim to minimize not only the number of vacant seats, but also the number of airline connections. The connected network with the least number of edges is a tree which has exactly n − 1 connections. However, the problem to construct a spanning tree with the minimum number of vacant seats is NP-complete. We also propose efficient approximation algorithms to construct a spanning tree with the minimum number of vacant seats.
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 1-round case) are well investigated. We introduce the discrete Voronoi game of which the game arena is given as a graph. We first show the best strategy when the game arena is a large complete k-ary tree. Next we show that the discrete Voronoi game is intractable in general. Even in 1-round case, and the place occupied by the first player is fixed, the game is NP-complete in general. We also show that the game is PSPACE-complete in general case. Key words: Voronoi Game, NP-completeness, PSPACE-completeness. 1
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 graph is proposed in this note. The decomposition gives a linear structure of bipartite permutation graphs, and it can be obtained in O(n) time, where n is the number of vertices. As an application of the decomposition, we show an O(n) time and space algorithm for finding a longest path in a bipartite permutation graph.
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 whether a graph admits a tree t-spanner, given t. We first substantially strengthen the known results for bipartite graphs. We prove that the tree t-spanner problem is NP-complete even for chordal bipartite graphs for t ≥ 5, and every bipartite ATE-free graph has a tree 3-spanner, which can be found in linear time. The previous best known results were NP-completeness for general bipartite graphs, and that every convex graph has a tree 3-spanner. We next focus on the tree t-spanner problem for probe interval graphs and related graph classes. The graph classes were introduced to deal with the physical mapping of DNA. From a graph theoretical point of view, the classes are natural generalizations of interval graphs. We show that these classes are tree 7-spanner admissible, and a tree 7-spanner can be constructed in O(m log n) time. Key Words. Chordal bipartite graph, Interval bigraph, NP-completeness, Probe interval graph, Tree spanner. 1. Introduction. A
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 graph class are known. However, the complexity of the graph isomorphism problem for the class is still unknown. In this paper, extended MPQ-trees are proposed to represent the interval probe graphs. An extended MPQtree is canonical and represents all possible permutations of the intervals. The extended MPQ-tree can be constructed from a given interval probe graph in O(n 2 + m) time. Thus we can solve the graph isomorphism problem for the interval probe graphs in O(n 2 + m) time. Using the tree, we can determine that any two nonprobes are independent, overlapping, or their relation cannot be determined without an experiment. Therefore, we can heuristically find the best nonprobe that would be probed in the next experiment. Also, we can enumerate all possible affirmative interval graphs for any interval probe graph.
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 can also be seen as a natural generalization of block graphs (and hence trees). In this paper, a new characterization of ptolemaic graphs is presented. It is a canonical tree representation based on a laminar structure of cliques. The tree representation is constructed in linear time from a perfect elimination ordering obtained by the lexicographic breadth first search. Hence recognition and graph isomorphism for ptolemaic graphs can be solved in linear time. The tree representation also gives a simple intersection model for ptolemaic graphs. The results are also extended to distance hereditary graphs.
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 algorithm for counting the number of independent sets; (2) a linear-time algorithm for counting the number of maximum independent sets; (3) a polynomial-time algorithm for counting the number of independent sets of a fixed size. With similar ideas, we show that enumeration (namely, listing) of the independent sets, the maximum independent sets, and the independent sets of a fixed size in a chordal graph can be done in constant amortized time per output. On the other hand, we prove that the following problems for a chordal graph are #P-complete: (1) counting the number of maximal independent sets; (2) counting the number of minimum maximal independent sets. With similar ideas, we also show that finding a minimum weighted maximal independent set in a chordal graph is NP-hard, and even hard to approximate. Keywords: chordal graph, counting, enumeration, independent set, NP-completeness, #P-completeness, polynomial time algorithm.
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 whether a graph admits a tree t-spanner, given t. We first substantially strengthen the known results for bipartite graphs. We prove that the tree t-spanner problem is NP-complete even for chordal bipartite graphs for t ≥ 5, and every bipartite ATE-free graph has a tree 3-spanner, which can be found in linear time. The previous best known results were NP-completeness for general bipartite graphs, and that every convex graph has a tree 3-spanner. We next focus on the tree t-spanner problem for probe interval graphs and related graph classes. The graph classes were introduced to deal with the physical mapping of DNA. From a graph theoretical point of view, the classes are natural generalizations of interval graphs. We show that these classes are tree 7-spanner admissible, and a tree 7-spanner can be constructed in O(m log n) time. Key Words. Chordal bipartite graph, Interval bigraph, NP-completeness, Probe interval graph, Tree spanner. 1. Introduction. A
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 inputs. For classes F consisting of functions which may be obtained from one function g on n inputs by replacing arbitrary n \Gamma k inputs by given constants this problem is known as attribute-efficient learning with k essential attributes. Results on general classes of functions are known. More precise and often optimal results are presented for the cases where g is one of the functions disjunction, parity or threshold.
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 length (LDPL), which is introduced in the paper, is a better measure than previously known one. The parallel complexity of the LFMIS problem on a graph gradually increases as the value measured on the graph grows: The LFMIS problem on a graph of LDPL O(log k n) is in NC k+1, and the problem on a graph of LDPL 2(n ffl) is P-complete. We also investigate the limit of the measure. We construct a kind of the lexicographically first maximal subgraph problems such that the problem is P-complete even if the LDPL of the input graph is restricted to 1. Finally we discuss the probability that a random graph has LDPL l and show that its threshold value is l n. This implies that a random graph of which each edge exists with probability p has LDPL 2(np) with high probability. The result also show the limit of the LDPL on the average case. Keywords: Analysis of algorithms, NC algorithms, P-completeness, the lexicographically first maximal subgraph problems, threshold function of a random graph. 1
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 produces only (and all) \unique solution instances", i.e., instances with only one solution. In this paper, we consider two simple instance generation algorithms, and estimate the number of clauses required by the algorithms to generate unique solution instances with high probability.
Key words: Analysis of algorithms, upper/lower bounds of problems, randomized
Abstract. 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 is randomized and runs in O(log n) expected time using n 2 processors on a CRCW PRAM. The second one is deterministic and runs in O(log 2 n) time using n 4 processors on an EREW PRAM. The last one is deterministic and runs in O(log 5 n) time using n
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 lexicographically first maximal subgraph (LFMS) problems. That is, the parallel complexity of the problems gradually increases as the value measured on a graph grows; the LFMS problems are in NC on graphs of LDPL O(log