研究者詳細 - 斎藤　寿樹

論文 - 斎藤　寿樹

分割表示73 件中 1 - 20 件目／全件表示 >>

Efficient non-isomorphic graph enumeration algorithms for several intersection graph classes 招待有り査読有り国際誌

Kawahara J., Saitoh T., Takeda H., Yoshinaka R., Yoshioka Y.

Theoretical Computer Science 1003 2024年07月

担当区分：責任著者記述言語：英語掲載種別：研究論文（学術雑誌）

Intersection graphs are well-studied in the area of graph algorithms. Some intersection graph classes are known to have algorithms enumerating all unlabeled graphs by reverse search. Since these algorithms output graphs one by one and the numbers of graphs in these classes are vast, they work only for a small number of vertices. Binary decision diagrams (BDDs) are compact data structures for various types of data and useful for solving optimization and enumeration problems. This study proposes enumeration algorithms for five intersection graph classes, which admit O(n)-bit string representations for their member graphs. Our algorithm for each class enumerates all unlabeled graphs with n vertices over BDDs representing the binary strings in time polynomial in n. Moreover, our algorithms are extended so that it enumerates those with constraints on the maximum (bi)clique size and/or the number of edges.

DOI： 10.1016/j.tcs.2024.114591

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

Overlapping edge unfoldings for convex regular-faced polyhedra 招待有り査読有り国際誌

Shiota T., Saitoh T.

Theoretical Computer Science 1002 2024年06月

担当区分：最終著者記述言語：英語掲載種別：研究論文（学術雑誌）

Herein, we discuss the existence of overlapping edge unfoldings for convex regular-faced polyhedra. Horiyama and Shoji showed that there are no overlapping edge unfoldings for all platonic solids and five of the Archimedean solids. The remaining five Archimedean solids were found to have edge unfoldings that overlap. In this study, we propose a method called rotational unfolding to find an overlapping edge unfolding of a polyhedron. We show that all the edge unfoldings of an icosidodecahedron, a rhombitruncated cuboctahedron, an n-gonal Archimedean prism (3≤n≤23), an m-gonal Archimedean antiprism (3≤m≤11), and 48 types of Johnson solids do not overlap. Our algorithm finds overlapping edge unfoldings for the snub cube, and 44 types of Johnson solids. We present analytic proof that an overlapping edge unfolding exists in an n-gonal Archimedean prism (n≥24), and an m-gonal Archimedean antiprism (m≥12). Our results prove the existence of overlapping edge unfoldings for convex regular-faced polyhedra.

DOI： 10.1016/j.tcs.2024.114593

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

Sorting balls and water: Equivalence and computational complexity 招待有り査読有り国際誌

Ito T., Kawahara J., Minato S.i., Otachi Y., Saitoh T., Suzuki A., Uehara R., Uno T., Yamanaka K., Yoshinaka R.

Theoretical Computer Science 978 2023年11月

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

Various forms of sorting problems have been studied over the years. Recently, two kinds of sorting puzzle apps have gained popularity. In these puzzles, we are given a set of bins filled with colored units, balls or water, and some empty bins. These puzzles allow us to move colored units from a bin to another when the colors involved match in some way or the target bin is empty. The goal of these puzzles is to sort all the color units in order. We investigate computational complexities of these puzzles. We first show that these two puzzles are essentially the same from the viewpoint of solvability. That is, an instance is sortable by ball-moves if and only if it is sortable by water-moves. We also show that every yes-instance has a solution of polynomial length, which implies that these puzzles belong to NP. We then show that these puzzles are NP-complete. For some special cases, we give polynomial-time algorithms. We finally consider the number of empty bins sufficient for making all instances solvable and give non-trivial upper and lower bounds in terms of the number of filled bins and the capacity of bins.

DOI： 10.1016/j.tcs.2023.114158

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

Efficient Non-isomorphic Graph Enumeration Algorithms for Subclasses of Perfect Graphs 査読有り国際誌

Kawahara J., Saitoh T., Takeda H., Yoshinaka R., Yoshioka Y.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 13973 LNCS 151 - 163 2023年01月

担当区分：責任著者記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

Intersection graphs are well-studied in the area of graph algorithms. Some intersection graph classes are known to have algorithms enumerating all unlabeled graphs by reverse search. Since these algorithms output graphs one by one and the numbers of graphs in these classes are vast, they work only for a small number of vertices. Binary decision diagrams (BDDs) are compact data structures for various types of data and useful for solving optimization and enumeration problems. This study proposes enumeration algorithms for five intersection graph classes, which admit -bit string representations for their member graphs. Our algorithm for each class enumerates all unlabeled graphs with n vertices over BDDs representing the binary strings in time polynomial in n. Moreover, our algorithms are extended to enumerate those with constraints on the maximum (bi)clique size and/or the number of edges.

DOI： 10.1007/978-3-031-27051-2_14

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

Path Cover Problems with Length Cost 査読有り

Kobayashi K., Lin G., Miyano E., Saitoh T., Suzuki A., Utashima T., Yagita T.

Algorithmica 85 ( 11 ) 3348 - 3375 2023年01月

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

For a graph G= (V, E) , a collection P of vertex-disjoint (simple) paths is called a path cover of G if every vertex v∈ V is contained in exactly one path of P. The Path Cover problem (PC for short) is to find a minimum cardinality path cover of G. In this paper, we introduce generalizations of PC, where each path is associated with a weight (cost or profit). Our problem, Minimum (Maximum) Weighted Path Cover [MinPC (MaxPC)], is defined as follows: Let U= { 0 , 1 , ⋯ , n- 1 }. Given a graph G= (V, E) and a weight function f: U→ R∪ { + ∞, - ∞} that defines a weight for each path based on its length, the objective of MinPC (MaxPC) is to find a path cover P of G such that the total weight of the paths in P is minimized (maximized). Let L be a subset of U, and PL be the set of paths such that each path is of length ℓ∈ L. We consider MinPLPC with binary cost, i.e., the cost function is f(ℓ) = 1 if ℓ∈ L; otherwise, f(ℓ) = 0. We also consider MaxPLPC with f(ℓ) = ℓ+ 1 , if ℓ∈ L; otherwise, f(ℓ) = 0. Many well-known graph theoretic problems such as the Hamiltonian Path and the Maximum Matching problems can be modeled using MinPLPC and MaxPLPC. In this paper, we first show that deciding whether MinP{ 0 , 1 , 2 }PC has a 0-weight solution is NP-complete for planar bipartite graphs of maximum degree three, and consequently, (i) for any constant σ≥ 1 , there is no polynomial-time approximation algorithm with approximation ratio σ for MinP{ 0 , 1 , 2 }PC unless P = NP, and (ii) MaxP{3,⋯,n-1}PC is NP-hard for the same graph class. Next, we present a polynomial-time algorithm for MinP{,1,⋯,k}PC on graphs with bounded treewidth for a fixed k. Lastly, we present a 4-approximation algorithm for MaxP{3,⋯,n-1}PC, which becomes a 2.5-approximation algorithm for subcubic graphs.

DOI： 10.1007/s00453-023-01106-2

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

Overlapping Edge Unfoldings for Archimedean Solids and (Anti)prisms 査読有り国際誌

Shiota T., Saitoh T.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 13973 LNCS 36 - 48 2023年01月

担当区分：最終著者記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

Herein, we discuss the existence of overlapping edge unfoldings for Archimedean solids and (anti)prisms. Horiyama and Shoji showed that there are no overlapping edge unfoldings for all platonic solids and five shapes of Archimedean solids. The remaining five Archimedean solids were also found to have edge unfoldings that overlap. In this study, we propose a method called rotational unfolding to find an overlapping edge unfolding of a polyhedron. We show that all the edge unfoldings of an icosidodecahedron, a rhombitruncated cuboctahedron, an n-gonal Archimedean prism, and an m-gonal Archimedean antiprism do not overlap when and. Our algorithm finds three types of overlapping edge unfoldings for a snub cube, consisting of two vertices in contact. We show that an overlapping edge unfolding exists in an n-gonal Archimedean prism and an m-gonal Archimedean antiprism for and. Our results prove the existence of overlapping edge unfoldings for Archimedean solids and Archimedean (anti)prisms.

DOI： 10.1007/978-3-031-27051-2_4

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

Sorting Balls and Water: Equivalence and Computational Complexity 査読有り国際誌

Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Yota Otachi, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka, Ryo Yoshinaka

LIPIcs–Leibniz International Proceedings in Informatics ( Schloss Dagstuhl ) 226 16:1 - 16:17 2022年05月

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

Italy Sicily 2022年05月30日 - 2022年06月03日

Various forms of sorting problems have been studied over the years. Recently, two kinds of sorting puzzle apps are popularized. In these puzzles, we are given a set of bins filled with colored units, balls or water, and some empty bins. These puzzles allow us to move colored units from a bin to another when the colors involved match in some way or the target bin is empty. The goal of these puzzles is to sort all the color units in order. We investigate computational complexities of these puzzles. We first show that these two puzzles are essentially the same from the viewpoint of solvability. That is, an instance is sortable by ball-moves if and only if it is sortable by water-moves. We also show that every yes-instance has a solution of polynomial length, which implies that these puzzles belong to NP. We then show that these puzzles are NP-complete. For some special cases, we give polynomial-time algorithms. We finally consider the number of empty bins sufficient for making all instances solvable and give non-trivial upper and lower bounds in terms of the number of filled bins and the capacity of bins.

DOI： 10.4230/LIPIcs.FUN.2022.16

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

Path Cover Problems with Length Cost 査読有り国際誌

Kenya Kobayashi, Guohui Lin, Eiji Miyano, Toshiki Saitoh, Akira Suzuki, Tadatoshi Utashima, Tsuyoshi Yagita

Lecture Notes in Computer Science ( Springer ) 13174 396 - 408 2022年03月

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

Indonesia Jember 2022年03月24日 - 2022年03月26日

For a graph G= (V, E), a collection P of vertex-disjoint (simple) paths is called a path cover of G if every vertex v∈ V is contained in exactly one path of P. The Path Cover problem (PC for short) is to find a minimum cardinality path cover of G. In this paper, we introduce generalizations of PC, where each path is associated with a weight (cost or profit). Our problem, Minimum (Maximum) Weighted Path Cover (MinPC (MaxPC)), is defined as follows: Let U= { 0, 1, ⋯, n- 1 }. Given a graph G= (V, E) and a weight function f: U→ R∪ { + ∞, - ∞}, which defines a weight for each path in its length, MinPC (MaxPC) is to find a path cover P of G such that the total weight of the paths in P is minimized (maximized). Let L be a subset of U, and PL be the set of paths such that each path is of length ℓ∈ L. We especially consider MinPLPC with 0–1 cost, i.e., the cost function is f(ℓ) = 1 if ℓ∈ L; otherwise f(ℓ) = 0. We also consider MaxPLPC with f(ℓ) = ℓ+ 1, if ℓ∈ L; otherwise f(ℓ) = 0. That is, MaxPLPC is to maximize the number of vertices contained in the paths with length ℓ∈ L in a path cover. In this paper, we first show that MinP{ 0, 1, 2 }PC is NP-hard for planar bipartite graphs of maximum degree three. This implies that (i) for any constant σ≥ 1, there is no polynomial-time approximation algorithm with approximation ratio σ for MinP{ 0, 1, 2 }PC unless P = NP, and (ii) MaxP{3,⋯,n-1}PC is NP-hard for the same graph class. Next, (iii) we present a polynomial-time algorithm for MinP{0,1,⋯,k}PC on graphs with bounded treewidth for a fixed k. Lastly, (iv) we present a 4-approximation algorithm for MaxP{3,⋯,n-1}PC, which becomes a 2.5-approximation for subcubic graphs.

DOI： 10.1007/978-3-030-96731-4_32

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

Max-Min 3-dispersion Problems 査読有り

HORIYAMA Takashi, NAKANO Shin-ichi, SAITOH Toshiki, SUETSUGU Koki, SUZUKI Akira, UEHARA Ryuhei, UNO Takeaki, WASA Kunihiro

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences ( 一般社団法人電子情報通信学会 ) 2021年01月

担当区分：責任著者記述言語：英語掲載種別：研究論文（学術雑誌）

<p>Given a set <i>P</i> of <i>n</i> points on which facilities can be placed and an integer <i>k</i>, we want to place <i>k</i> facilities on some points so that the minimum distance between facilities is maximized. The problem is called the <i>k</i>-dispersion problem. In this paper, we consider the 3-dispersion problem when <i>P</i> is a set of points on a plane (2-dimensional space). Note that the 2-dispersion problem corresponds to the diameter problem. We give an <i>O</i>(<i>n</i>) time algorithm to solve the 3-dispersion problem in the <i>L</i><sub>∞</sub> metric, and an <i>O</i>(<i>n</i>) time algorithm to solve the 3-dispersion problem in the <i>L</i><sub>1</sub> metric. Also, we give an <i>O</i>(<i>n</i><sup>2</sup> log <i>n</i>) time algorithm to solve the 3-dispersion problem in the <i>L</i><sub>2</sub> metric.</p>

DOI： 10.1587/transfun.2020DMP0003

その他リンク： https://ci.nii.ac.jp/naid/130008000342

Fixed-Treewidth-Efficient Algorithms for Edge-Deletion to Interval Graph Classes 査読有り国際誌

Saitoh T., Yoshinaka R., Bodlaender H.L.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 12635 LNCS 142 - 153 2021年01月

担当区分：筆頭著者,　責任著者記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

For a graph class C, the C -Edge-Deletion problem asks for a given graph G to delete the minimum number of edges from G in order to obtain a graph in C. We study the C -Edge-Deletion problem for C the class of interval graphs and other related graph classes. It follows from Courcelle’s Theorem that these problems are fixed parameter tractable when parameterized by treewidth. In this paper, we present concrete FPT algorithms for these problems. By giving explicit algorithms and analyzing these in detail, we obtain algorithms that are significantly faster than the algorithms obtained by using Courcelle’s theorem.

DOI： 10.1007/978-3-030-68211-8_12

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

Complexity of the maximum k-path vertex cover problem 査読有り

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

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences ( 一般社団法人電子情報通信学会 ) E103A ( 10 ) 1193 - 1201 2020年10月

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

Copyright © 2020 The Institute of Electronics, Information and Communication Engineers This paper introduces the maximization version of the kpath 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 Pk includes a vertex v in a vertex set S, then we say that v or S covers Pk. Given a graph G = (V, E) and an integer s, the goal of MaxPkVC is to find a vertex subset S ⊆ V of at most s vertices such that the number of k-paths covered by S is maximized. The problem MaxPkVC is generally NP-hard. In this paper we consider the tractability/intractability of MaxPkVC on subclasses of graphs. We prove that MaxP3VC remains NP-hard even for split graphs. Furthermore, if the input graph is restricted to graphs with constant bounded treewidth, then MaxP3VC can be solved in polynomial time.

DOI： 10.1587/transfun.2019DMP0014

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

Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs 招待有り査読有り国際誌

Yamazaki K., Saitoh T., Kiyomi M., Uehara R.

Theoretical Computer Science ( ELSEVIER ) 806 310 - 322 2020年02月

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

© 2019 In this paper, a general framework for enumerating every element in a graph class is given. The main feature of this framework is that it is designed to enumerate only nonisomorphic graphs in a graph class. Applying this framework to the classes of interval graphs and permutation graphs, we give efficient enumeration algorithms for these graph classes such that each element in the class is output in a polynomial time delay. The experimental results are also given. The catalogs of graphs in these graph classes are also provided.

DOI： 10.1016/j.tcs.2019.04.017

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

The time complexity of permutation routing via matching, token swapping and a variant 招待有り査読有り

Kawahara J., Saitoh T., Yoshinaka R.

Journal of Graph Algorithms and Applications 23 ( 1 ) 29 - 70 2019年01月

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

© 2019, Brown University. All rights reserved. The problems of Permutation Routing via Matching and Token Swapping are reconfiguration problems on graphs. This paper is concerned with the complexity of those problems and a colored variant. For a given graph where each vertex has a unique token on it, those problems requirto find a shortest way to modify a token placement into another by swapping tokens on adjacent vertices. While all pairs of tokens on a matching can be exchanged at once in Permutation Routing via Matching, Token Swapping allows only one pair of tokens can be swapped. In the colored version, vertices and tokens are colored and the goal is to relocate tokenso that each vertex has a token of the same color. We investigate the timcomplexity of several restricted cases of those problems and show when those problems become tractable and remain intractable.

DOI： 10.7155/JGAA.00483

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85067628333&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.

Journal of Graph Algorithms and Applications 23 ( 1 ) 3 - 27 2019年01月

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

© 2019, Brown University. All rights reserved. We consider a puzzle consisting of colored tokens on an n-vertex 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.

DOI： 10.7155/JGAA.00482

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

Special section on discrete mathematics and its applications 査読有り

Kawachi A., Yamauchi Y., Ito T., Uchizawa K., Otachi Y., Ono H., Kimura K., Koga H., Saitoh T., Shibuya T., Takimoto E., Tanigawa S., Nuida K., Fukushima K., Fujiwara H., Mizuki T., Moriyama S., Sadakane K.

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E102A ( 9 ) 2019年01月

Max-Min 3-Dispersion Problems 査読有り

Horiyama T., Nakano S., Saitoh T., Suetsugu K., Suzuki A., Uehara R., Uno T., Wasa K.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 11653 LNCS 291 - 300 2019年01月

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

© Springer Nature Switzerland AG 2019. Given a set P of n points on which facilities can be placed and an integer k, we want to place k facilities on some points so that the minimum distance between facilities is maximized. The problem is called the k-dispersion problem. In this paper we consider the 3-dispersion problem when P is a set of points on a plane. Note that the 2-dispersion problem corresponds to the diameter problem. We give an O(n) time algorithm to solve the 3-dispersion problem in the (forumala presented). metric, and an O(n) time algorithm to solve the 3-dispersion problem in the (forumala presented) metric. Also we give an (forumala presented) time algorithm to solve the 3-dispersion problem in the (forumala presented) metric.

DOI： 10.1007/978-3-030-26176-4_24

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

Colorful Frontier-Based Search: Implicit Enumeration of Chordal and Interval Subgraphs 査読有り

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

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 11544 LNCS 125 - 141 2019年01月

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

© 2019, Springer Nature Switzerland AG. This paper considers enumeration of specific subgraphs of a given graph by using a data structure called a zero-suppressed binary decision diagram (ZDD). A ZDD can represent the set of solutions quite compactly. Recent studies have demonstrated that a technique generically called frontier-based search (FBS) is a powerful framework for using ZDDs to enumerate various yet rather simple types of subgraphs. We in this paper, propose colorful FBS, an enhancement of FBS, which enables us to enumerate more complex types of subgraphs than existing FBS techniques do. On the basis of colorful FBS, we design methods that construct ZDDs representing the sets of chordal and interval subgraphs from an input graph. Computer experiments show that the proposed methods run faster than reverse search based algorithms.

DOI： 10.1007/978-3-030-34029-2_9

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

Swapping colored tokens on graphs 招待有り査読有り

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

Theoretical Computer Science 729 1 - 10 2018年06月

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

© 2018 Elsevier B.V. We investigate the computational complexity of the following problem. We are given a graph in which each vertex has an initial and a target color. 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 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. Besides, we show that, the problem for complete graphs is fixed-parameter tractable when parameterized by the number of colors, while it is known to be NP-complete when the number of colors is unbounded.

DOI： 10.1016/j.tcs.2018.03.016

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

Exact algorithms for the max-min dispersion problem 査読有り

Akagi T., Araki T., Horiyama T., Nakano S., Okamoto Y., Otachi Y., Saitoh T., Uehara R., Uno T., Wasa K.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10823 LNCS 263 - 272 2018年01月

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

© 2018, Springer International Publishing AG, part of Springer Nature. Given a set P of n elements, and a function d that assigns a non-negative real number d(p, q) for each pair of elements (formula presented), we want to find a subset (formula presented) with (formula presented) such that (formula presented) is maximized. This is the max-min k-dispersion problem. In this paper, exact algorithms for the max-min k-dispersion problem are studied. We first show the max-min k-dispersion problem can be solved in (formula presented) time. Then, we show two special cases in which we can solve the problem quickly. Namely, we study the cases where a set of n points lie on a line and where a set of n points lie on a circle (and the distance is measured by the shortest arc length on the circle). We obtain O(n)-time algorithms after sorting.

DOI： 10.1007/978-3-319-78455-7_20

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

Enumeration of Nonisomorphic Interval Graphs and Nonisomorphic Permutation Graphs 査読有り

Yamazaki K., Saitoh T., Kiyomi M., Uehara R.

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

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

© 2018, Springer International Publishing AG, part of Springer Nature. In this paper, a general framework for enumerating every element in a graph class is given. The main feature of this framework is that it is designed to enumerate only non-isomorphic graphs in a graph class. Applying this framework to the classes of interval graphs and permutation graphs, we give efficient enumeration algorithms for these graph classes such that each element in the class is output in a polynomial time delay. The experimental results are also provided. The catalogs of graphs in these graph classes are also provided.

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

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

　前のページ- 次のページ　

1
2
3
4