研究者詳細 - 斎藤　寿樹

論文 - 斎藤　寿樹

分割表示73 件中 21 - 40 件目／全件表示 >>

Computational complexity of robot arm simulation problems 査読有り

Feng T., Horiyama T., Okamoto Y., Otachi Y., Saitoh T., Uno T., Uehara R.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10979 LNCS 177 - 188 2018年01月

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

© Springer International Publishing AG, part of Springer Nature 2018. We consider a simulation problem of a general mechanism by a robot arm. A robot arm can be modeled by a path P, and the target is modeled by a general graph G. Then the problem asks if there is an edge-weighted Eulerian path of G spanned by P. We first show that it is strongly NP-hard even if edge lengths are restricted. Then we consider two different variants of this problem. We first allow the edges in P to be elastic, and minimize the elastic ratio when G is a path. Second, we allow P to cover an edge of G twice or more. The problem is weakly NP-hard even if G is an edge. We thus assume that each edge of G is covered by P exactly twice, and obtain three hardness results and one polynomial-time algorithm when G and edge lengths are restricted.

DOI： 10.1007/978-3-319-94667-2_15

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85049910939&origin=inward

Complexity of the Maximum k-Path Vertex Cover Problem 査読有り

Miyano E., Saitoh T., Uehara R., Yagita T., van der Zanden T.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10755 LNCS 240 - 251 2018年01月

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

© 2018, Springer International Publishing AG, part of Springer Nature. This paper introduces the maximum version of the k-path vertex cover problem, called the Maximum k-Path Vertex Cover problem (MaxPkVC for short): A path consisting of k vertices, i.e., a path of length k-1 is called a k-path. If a k-path Pkincludes a vertex v in a vertex set S, then we say that S or v covers Pk. Given a graph G=(V,E) and an integer s, the goal of MaxPkVC is to find a vertex subset S=C of at most s vertices such that the number of k-paths covered by S is maximized. MaxPkVC is generally NP-hard. In this paper we consider the tractability/intractability of MaxPkVC on subclasses of graphs: We prove that MaxP3VC and MaxP4VC remain NP-hard even for split graphs and for chordal graphs, respectively. Furthermore, if the input graph is restricted to graphs with constant bounded treewidth, then MaxP3VC can be solved in polynomial time.

DOI： 10.1007/978-3-319-75172-6_21

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85043347936&origin=inward

ZDD と列挙問題 - 最新の技法とプログラミングツール査読有り

戸田貴久、斎藤寿樹, 岩下洋哲, 川原純, 湊真一

Computer Software 34 ( 3 ) 97 - 120 2017年08月

記述言語：英語掲載種別：研究論文（学術雑誌）

Combinatorial enumeration problems are to find all combinations of items (solutions) that satisfy given constraints. There are many applications to various problems that are closely related to real-life such as power distribution network analysis. Recent researches have paid attention to a generic framework for computing various combinatorial enumeration problems through the method of efficiently constructing the data structure, ZDD, for all solutions of those problems in a top-down fashion, which is thus called top-down ZDD construction. The paper focuses on this subject and provides a comprehensive survey on algorithms that the construction is based on, an extended method for efficiently handling complicated constraints, the basics of the programming tool, TdZdd, that allows us to easily develop top-down construction-based programs, and practical programming examples of some applied problems.

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85027134284&origin=inward

Extending Partial Representations of Interval Graphs 査読有り

Klavík P., Kratochvíl J., Otachi Y., Saitoh T., Vyskočil T.

Algorithmica 78 ( 3 ) 945 - 967 2017年07月

記述言語：英語掲載種別：研究論文（学術雑誌）

© 2016, Springer Science+Business Media New York. Interval graphs are intersection graphs of closed intervals of the real-line. The well-known computational problem, called recognition, asks whether an input graph G can be represented by closed intervals, i.e., whether G is an interval graph. There are several linear-time algorithms known for recognizing interval graphs, the oldest one is by Booth and Lueker (J Comput Syst Sci 13:335–379, 1976) based on PQ-trees. In this paper, we study a generalization of recognition, called partial representation extension. The input of this problem consists of a graph G with a partial representation R ′ fixing the positions of some intervals. The problem asks whether it is possible to place the remaining interval and create an interval representation R of the entire graph G extending R ′ . We generalize the characterization of interval graphs by Fulkerson and Gross (Pac J Math 15:835–855, 1965) to extendible partial representations. Using it, we give a linear-time algorithm for partial representation extension based on a reordering problem of PQ-trees.

DOI： 10.1007/s00453-016-0186-z

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84979285092&origin=inward

Fast maximum weight clique extraction algorithm: Optimal tables for branch-and-bound 査読有り

Shimizu S., Yamaguchi K., Saitoh T., Masuda S.

Discrete Applied Mathematics 223 120 - 134 2017年05月

記述言語：英語掲載種別：研究論文（学術雑誌）

© 2017 Elsevier B.V. A new branch-and-bound algorithm for the maximum weight clique problem is proposed. The proposed algorithm consists of two phases, a precomputation phase and a branch-and-bound phase. In the precomputation phase, the weights of maximum weight cliques in many small subgraphs are calculated and stored in optimal tables. In the branch-and-bound phase, each problem is divided into smaller subproblems, and unnecessary subproblems are pruned using the optimal tables. We performed experiments with the proposed algorithm and five existing algorithms for several types of graphs. The results indicate that only the proposed algorithm can obtain exact solutions for all graphs and that it performs much faster than other algorithms for nearly all graphs.

DOI： 10.1016/j.dam.2017.01.026

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85014188029&origin=inward

Extending Partial Representations of Proper and Unit Interval Graphs 査読有り

Klavík P., Kratochvíl J., Otachi Y., Rutter I., Saitoh T., Saumell M., Vyskočil T.

Algorithmica 77 ( 4 ) 1071 - 1104 2017年04月

記述言語：英語掲載種別：研究論文（学術雑誌）

© 2016, Springer Science+Business Media New York. The recently introduced problem of extending partial interval representations asks, for an interval graph with some intervals pre-drawn by the input, whether the partial representation can be extended to a representation of the entire graph. In this paper, we give a linear-time algorithm for extending proper interval representations and an almost quadratic-time algorithm for extending unit interval representations. We also introduce the more general problem of bounded representations of unit interval graphs, where the input constrains the positions of some intervals by lower and upper bounds. We show that this problem is NP-complete for disconnected input graphs and give a polynomial-time algorithm for the special class of instances, where the ordering of the connected components of the input graph along the real line is prescribed. This includes the case of partial representation extension. The hardness result sharply contrasts the recent polynomial-time algorithm for bounded representations of proper interval graphs (Balko et al. in 2013). So unless P= NP, proper and unit interval representations have vastly different structure. This explains why partial representation extension problems for these different types of representations require substantially different techniques.

DOI： 10.1007/s00453-016-0133-z

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84975783207&origin=inward

Ferrers dimension of grid intersection graphs 査読有り

Chaplick S., Hell P., Otachi Y., Saitoh T., Uehara R.

Discrete Applied Mathematics 216 130 - 135 2017年01月

記述言語：英語掲載種別：研究論文（学術雑誌）

© 2015 Elsevier B.V. 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.

DOI： 10.1016/j.dam.2015.05.035

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84931067125&origin=inward

The time complexity of the token swapping problem and its parallel variants 査読有り

Kawahara J., Saitoh T., Yoshinaka R.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10167 LNCS 448 - 459 2017年01月

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

© Springer International Publishing AG 2017. The token swapping problem (TSP) and its colored version are reconfiguration problems on graphs. This paper is concerned with the complexity of the TSP and two new variants; namely parallel TSP and parallel colored TSP. For a given graph where each vertex has a unique token on it, the TSP requires to find a shortest way to modify a token placement into another by swapping tokens on adjacent vertices. In the colored version, vertices and tokens are colored and the goal is to relocate tokens so that each vertex has a token of the same color. Their parallel versions allow simultaneous swaps on non-incident edges in one step. We investigate the time complexity of several restricted cases of those problems and show when those problems become tractable and remain intractable.

DOI： 10.1007/978-3-319-53925-6_35

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85014234196&origin=inward

Space-efficient and output-sensitive implementations of greedy algorithms on intervals 査読有り

Saitoh T., Kirkpatrick D.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10167 LNCS 320 - 332 2017年01月

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

© Springer International Publishing AG 2017. We consider the space-efficient implementation of greedy algorithms for several fundamental problems on intervals. We assume a random access machine model with read-only access to input stored in Θ(n) words of memory, augmented with a random access memory (workspace) of size Θ(s) bits, where lgn ≤ s ≤ n. Our implementations are based on the efficient realization of an abstract data structure that we call a temporal priority queue that supports extract-min and advancetime operations for a static collection of entities, each of which is active for some pre-specified interval of time. This realization is a generalization of the memory-adjustable navigation pile proposed by Asano et al. in studying time-space tradeoffs for sorting. Using temporal priority queues we are able to implement familiar greedy algorithms for the maximum independent set problem and a variety of dominating set problems on intervals, using O(m(lg (sk/m) + n/s)) time and Θ(s) bits of workspace, where k is the size of output and m = min(sk, n). Choosing s = Θ(n) this achieves O(n lg k) output-sensitive time complexity for the maximum independent set problem on intervals, previously realized using Ω(n) words of workspace.

DOI： 10.1007/978-3-319-53925-6_25

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85014136110&origin=inward

Solving the longest oneway-ticket problem and enumerating letter graphs by augmenting the two representative approaches with ZDDs 査読有り

Kawahara J., Saitoh T., Suzuki H., Yoshinaka R.

Advances in Intelligent Systems and Computing 532 294 - 305 2017年01月

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

© Springer International Publishing AG 2017. Several researchers have studied subgraph enumeration algorithms that use a compressed expression for a family of sets, called a zero-suppressed binary decision diagram (ZDD), to solve subgraph optimization problems. We have two representative approaches to manipulate ZDDs effectively. One is fundamental mathematical operations on families of sets over ZDDs. The other is a direct construction method of a ZDD that represents desired subgraphs of a graph and is called frontierbased search. In this research, we augment the approaches by proposing two new operations, called disjoint join and joint join, on family algebra over ZDDs and extending the frontier-based search to enumerate subgraphs that have a given number of vertices of specified degrees. Employing the new approaches, we present enumeration algorithms for alphabet letter graphs on a given graph. Moreover, we solve a variant of the longest path problem, called the Longest Oneway-ticket Problem (LOP), that requires computing the longest trip on the railway network of the Japan Railways Group using a oneway ticket. Numerical experiments show that our algorithm solves the LOP and is faster than the existing integer programming approach for some instances.

DOI： 10.1007/978-3-319-48517-1_26

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84994827378&origin=inward

Sequentially swapping colored tokens on graphs 査読有り

Yamanaka K., Demaine E., Horiyama T., Kawamura A., Nakano S., Okamoto Y., Saitoh T., Suzuki A., Uehara R., Uno T.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10167 LNCS 435 - 447 2017年01月

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

© Springer International Publishing AG 2017. We consider a puzzle consisting of colored tokens on an nvertex graph, where each token has a distinct starting vertex and a set of allowable target vertices for it to reach, and the only allowed transformation is to “sequentially” move the chosen token along a path of the graph by swapping it with other tokens on the path. This puzzle is a variation of the Fifteen Puzzle and is solvable in O(n 3 ) token-swappings. We thus focus on the problem of minimizing the number of token-swappings to reach the target token-placement. We first give an inapproximability result of this problem, and then show polynomial-time algorithms on trees, complete graphs, and cycles.

DOI： 10.1007/978-3-319-53925-6_34

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85014285826&origin=inward

頂点と辺の重なりを削除するグラフレイアウト調整アルゴリズム査読有り

塚本和樹, 増田澄男, 斎藤寿樹, 山口一章

電子情報通信学会論文誌 J99-A ( 12 ) 471 - 479 2016年12月

A fast heuristic for the minimum weight vertex cover problem 査読有り

Shimizu S., Yamaguchi K., Saitoh T., Masuda S.

2016 IEEE/ACIS 15th International Conference on Computer and Information Science, ICIS 2016 - Proceedings 2016年08月

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

© 2016 IEEE. Given a vertex-weighted undirected graph, to find the vertex cover of minimum weight is called minimum weight vertex cover problem (MWVCP). It is known as an NP-hard problem. In this paper, a fast heuristic for MWVCP is proposed. Our algorithm is based on a simple algorithm called 'list-heuristic.' Experimenal results show that our algorithm calculates better solutions in shorter time than approximation algorithms for MWVCP.

DOI： 10.1109/ICIS.2016.7550782

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84987981842&origin=inward

Swapping labeled tokens on graphs 査読有り

Yamanaka K., Demaine E., Ito T., Kawahara J., Kiyomi M., Okamoto Y., Saitoh T., Suzuki A., Uchizawa K., Uno T.

Theoretical Computer Science 586 81 - 94 2015年06月

記述言語：英語掲載種別：研究論文（学術雑誌）

© 2015 Elsevier B.V. Consider a puzzle consisting of n tokens on an n-vertex graph, where each token has a distinct starting vertex and a distinct target vertex it wants to reach, and the only allowed transformation is to swap the tokens on adjacent vertices. We prove that every such puzzle is solvable in O(n 2 ) token swaps, and thus focus on the problem of minimizing the number of token swaps to reach the target token placement. We give a polynomial-time 2-approximation algorithm for trees, and using this, obtain a polynomial-time 2α-approximation algorithm for graphs whose tree α-spanners can be computed in polynomial time. Finally, we show that the problem can be solved exactly in polynomial time on complete bipartite graphs.

DOI： 10.1016/j.tcs.2015.01.052

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84945293281&origin=inward

階層グラフ描画における道の移動処理を用いた頂点順序決定法査読有り

的場郁典, 増田澄男, 荒木徹也, 斎藤寿樹, 山口一章

電子情報通信学会論文誌 J98-A ( 1 ) 152 - 164 2015年01月

Swapping colored tokens on graphs 査読有り

Yamanaka K., Horiyama T., Kirkpatrick D., Otachi Y., Saitoh T., Uehara R., Uno Y.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 9214 619 - 628 2015年01月

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

© Springer International Publishing Switzerland 2015. We investigate the computational complexity of the following problem. We are given a graph in which each vertex has the current and target colors. Each pair of adjacent vertices can swap their current colors. Our goal is to perform the minimum number of swaps so that the current and target colors agree at each vertex. When the colors are chosen from {1, 2,..., c}, we call this problem c-COLORED TOKEN SWAPPING since the current color of a vertex can be seen as a colored token placed on the vertex. We show that c-COLORED TOKEN SWAPPING is NP-complete for every constant c ≥ 3 even if input graphs are restricted to connected planar bipartite graphs of maximum degree 3. We then show that 2-COLORED TOKEN SWAPPING can be solved in polynomial time for general graphs and in linear time for trees.

DOI： 10.1007/978-3-319-21840-3_51

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84951828706&origin=inward

Extending partial representations of subclasses of chordal graphs 査読有り

Klavík P., Kratochvíl J., Otachi Y., Saitoh T.

Theoretical Computer Science 576 ( 1 ) 85 - 101 2015年01月

記述言語：英語掲載種別：研究論文（学術雑誌）

© 2015 Elsevier B.V. Chordal graphs are intersection graphs of subtrees of a tree T. We investigate the complexity of the partial representation extension problem for chordal graphs. A partial representation specifies a tree T < sup > ' < /sup > and some pre-drawn subtrees of T < sup > ' < /sup > . It asks whether it is possible to construct a representation inside a modified tree T which extends the partial representation (i.e., keeps the pre-drawn subtrees unchanged).We consider four modifications of T < sup > ' < /sup > leading to vastly different problems: (i) T=T < sup > ' < /sup > , (ii) T is a subdivision of T < sup > ' < /sup > , (iii) T is a supergraph of T < sup > ' < /sup > , and (iv) T < sup > ' < /sup > is a topological minor of T. In some cases, it is interesting to consider the complexity even when just T < sup > ' < /sup > is given and no subtree is pre-drawn. Also, we consider three well-known subclasses of chordal graphs: Proper interval graphs, interval graphs and path graphs. We give an almost complete complexity characterization. We further study the parametrized complexity of the problems when parametrized by the number of pre-drawn subtrees, the number of components of the input graph G and the size of the tree T < sup > ' < /sup > .We describe an interesting relation with integer partition problems. The problem 3-Partition is used for all NP-completeness reductions. When the space in T < sup > ' < /sup > is limited, partial representation extension of proper interval graphs is "equivalent" to the BINPACKING problem.

DOI： 10.1016/j.tcs.2015.02.007

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84930241571&origin=inward

Competitive diffusion on weighted graphs 査読有り

Ito T., Otachi Y., Saitoh T., Satoh H., Suzuki A., Uchizawa K., Uehara R., Yamanaka K., Zhou X.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 9214 422 - 433 2015年01月

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

© Springer International Publishing Switzerland 2015. Consider an undirected and vertex-weighted graph modeling a social network, where the vertices represent individuals, the edges do connections among them, and weights do levels of importance of individuals. In the competitive diffusion game, each of a number of players chooses a vertex as a seed to propagate his/her idea which spreads along the edges in the graph. The objective of every player is to maximize the sum of weights of vertices infected by his/her idea. In this paper, we study a computational problem of asking whether a pure Nash equilibrium exists in a given graph, and present several negative and positive results with regard to graph classes. We first prove that the problem is W[1]-hard when parameterized by the number of players even for unweighted graphs. We also show that the problem is NP-hard even for series-parallel graphs with positive integer weights, and is NP-hard even for forests with arbitrary integer weights. Furthermore, we show that the problem for forests of paths with arbitrary weights is solvable in pseudo-polynomial time; and it is solvable in quadratic time if a given graph is unweighted. We also prove that the problem is solvable in polynomial time for chain graphs, cochain graphs, and threshold graphs with arbitrary integer weights.

DOI： 10.1007/978-3-319-21840-3_35

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84951793058&origin=inward

辺交差数が少ない階層グラフ描画作成のためのダミー頂点共有処理査読有り

堀尾明久, 増田澄男, 荒木徹也, 斎藤寿樹, 山口一章

電子情報通信学会論文誌 J97-A ( 11 ) 704 - 707 2014年11月

Exact Algorithms for B-Bandwidth Problem with Restricted B 査読有り

Hiroshi Yukumoto, Toshiki Saitoh, Kazuaki Yamaguchi, and Sumio Masuda

Proceedings of the KOREA-JAPAN Joint Workshop on Algorithms and Computation 44 - 49 2014年07月

　前のページ - 次のページ　

1
2
3
4