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

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

Scopus

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

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

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

Scopus

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

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

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

Scopus

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

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

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

Scopus

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

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

<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>_∞ metric, and an <i>O</i>(<i>n</i>) time algorithm to solve the 3-dispersion problem in the <i>L</i>₁ metric. Also, we give an <i>O</i>(<i>n</i>² log <i>n</i>) time algorithm to solve the 3-dispersion problem in the <i>L</i>₂ metric.</p>

DOI： 10.1587/transfun.2020DMP0003

CiNii Article

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

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

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

Scopus

CiNii Article

CiNii Research

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

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

© 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

Scopus

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

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

© 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

Scopus

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

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

© 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

Scopus

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

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

© 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

Scopus

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

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

© 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

Scopus

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

記述言語：英語   掲載種別：記事・総説・解説・論説等（その他）

DOI： 10.1587/transfun.E102.A.986

Scopus

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

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

© 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

Scopus

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

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

© 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

Scopus

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

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

© 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

Scopus

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

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

© 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

Scopus

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

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

© 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

Scopus

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

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

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.

Kyutacar

Scopus

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

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

© 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

Scopus

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

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

© 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

Scopus

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

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

© 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

Scopus

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

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

© 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

Scopus

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

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

© 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

Scopus

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

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

© 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

Scopus

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

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

© 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

Scopus

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

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

© 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

Scopus

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

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

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

© 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

Scopus

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

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

© 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

Scopus

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

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

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

© 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

Scopus

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

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

© 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

Scopus

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

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

© 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

Scopus

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

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

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

Kyutacar

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

We consider the problem of determining the path-distance-width for AT-free graphs and graphs in related classes such as k-cocomparability graphs, proper interval graphs, cobipartite graphs, and cochain graphs. We first show that the problem is NP-hard even for cobipartite graphs, and thus for AT-free graphs. Next we present simple approximation algorithms with constant approximation ratios for AT-free graphs and graphs in the related graph classes mentioned above. For instance, our algorithm for AT-free graphs has approximation factor 3 and runs in linear time. We also show that the problem is solvable in polynomial time for cochain graphs, which form a subclass of the class of proper interval graphs. © 2013 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2012.11.015

Scopus

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

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

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

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. © 2014 Springer International Publishing.

DOI： 10.1007/978-3-319-07890-8_31

Scopus

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

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

We introduce a concept of intersection dimension of a graph with respect to a graph class. This generalizes Ferrers dimension, boxicity, and poset dimension, and leads to interesting new problems. We focus in particular on bipartite graph classes defined as intersection graphs of two kinds of geometric objects. We relate well-known graph classes such as interval bigraphs, two-directional orthogonal ray graphs, chain graphs, and (unit) grid intersection graphs with respect to these dimensions. As an application of these graph-theoretic results, we show that the recognition problems for certain graph classes are NP-complete. © 2014 Springer International Publishing Switzerland.

DOI： 10.1007/978-3-319-06089-7_23

Scopus

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

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

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 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 a special class of instances, where the ordering of the connected components of the input graph along the real line is fixed. 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. ISAAC'13]. So unless P = NP, proper and unit interval representations have very different structure. This explains why partial representation extension problems for these different types of representations require substantially different techniques. © 2014 Springer International Publishing.

DOI： 10.1007/978-3-319-08404-6_22

Scopus

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

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

There are many folded states consistent with a given mountain-valley pattern of equidistant creases on a long paper strip. We would like to fold a paper strip such that the number of paper layers between each pair of hinged paper segments, called the crease width at the crease point, is minimized. This problem is called the stamp folding problem and there are two variants of this problem: minimization of the maximum crease width, and minimization of the total crease width. This optimization problem was recently introduced and investigated from the viewpoint of the counting problem. However, its computational complexity is not known. In this paper, we first show that the minimization problem of the maximum crease width is strongly NP-complete. Hence we cannot solve the problem in polynomial time unless P=NP. We next propose an algorithm that solves the minimization problem. The algorithm itself is a straightforward one, but its analysis is not trivial. We show that this algorithm runs in O((k+1) k n) time where n is the number of creases and k is the total crease width. © 2012 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.tcs.2012.08.006

Scopus

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

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

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

PREIMAGE CONSTRUCTION problem by Kratsch and Hemaspaandra naturally arose from the famous graph reconstruction conjecture. It deals with the algorithmic aspects of the conjecture. We present an O(n 8 ) time algorithm for PREIMAGE CONSTRUCTION on permutation graphs and an O(n 4 (n + m)) time algorithm for PREIMAGE CONSTRUCTION on distance-hereditary graphs, where n is the number of graphs in the input, and m is the number of edges in a preimage. Since each graph of the input has n - 1 vertices and O(n 2 ) edges, the input size is O(n 3 ) (, or O(nm)). There are polynomial time isomorphism algorithms for permutation graphs and distance-hereditary graphs. However the number of permutation (distance-hereditary) graphs obtained by adding a vertex to a permutation (distance-hereditary) graph is generally exponentially large. Thus exhaustive checking of these graphs does not achieve any polynomial time algorithm. Therefore reducing the number of preimage candidates is the key point. Copyright © 2013 The Institute of Electronics, Information and Communication Engineers.

DOI： 10.1587/transinf.E96.D.426

Scopus

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

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

Chordal graphs are intersection graphs of subtrees in a tree. We investigate complexity of the partial representation extension problem for chordal graphs. A partial representation specifies a tree T′ and some pre-drawn subtrees. It asks whether it is possible to construct a representation inside a modified tree T which extends the partial representation (keeps the pre-drawn subtrees unchanged). We consider four modifications of T′ and get vastly different problems. In some cases, the problem is interesting even if just T′ 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. In addition, we study parametrized complexity by the number of predrawn subtrees, the number of components and the size of the tree T′. We describe an interesting relation with integer partition problems. The problem3-PARTITION is used in theNP-completeness reductions. The BINPACKING problem is closely related to the extension of interval graphswhen space in T′ is limited, and we obtain "equivalency" with BINPACKING. © Springer-Verlag 2012.

Scopus

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

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

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

Thailand   Phuket  

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

We investigate the computational complexity of the following restricted variant of Subgraph Isomorphism: given a pair of connected graphs G=(V G ,E G ) and H=(V H ,E H ), determine if H is isomorphic to a spanning subgraph of G. The problem is NP-complete in general, and thus we consider cases where G and H belong to the same graph class such as the class of proper interval graphs, of trivially perfect graphs, and of bipartite permutation graphs. For these graph classes, several restricted versions of Subgraph Isomorphism such as Hamiltonian Path, Clique, Bandwidth, and Graph Isomorphism can be solved in polynomial time, while these problems are hard in general. © 2012 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disc.2012.07.010

Scopus

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

記述言語：日本語   掲載種別：記事・総説・解説・論説等（学術雑誌）

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

We study a character-based phylogeny reconstruction problem when an incomplete set of data is given. More specifically, we consider the situation under the directed perfect phylogeny assumption with binary characters in which for some species the states of some characters are missing. Our main object is to give an efficient algorithm to enumerate (or list) all perfect phylogenies that can be obtained when the missing entries are completed. While a simple branch-and-bound algorithm (B & B) shows a theoretically good performance, we propose another approach based on a zero-suppressed binary decision diagram (ZDD). Experimental results on randomly generated data exhibit that the ZDD approach outperforms B & B. We also prove that counting the number of phylogenetic trees consistent with a given data is #P-complete, thus providing an evidence that an efficient random sampling seems hard. © 2012 Springer-Verlag.

DOI： 10.1007/978-3-642-30850-5_22

Scopus

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

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

DOI： 10.1142/S1793830912500395

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

Link puzzles involve finding paths or a cycle in a grid that satisfy given local and global properties. This paper proposes algorithms that enumerate solutions and instances of two link puzzles, Slitherlink and Numberlink, by zero-suppressed binary decision diagrams (ZDDs). A ZDD is a compact data structure for a family of sets provided with a rich family of set operations, by which, for example, one can easily extract a subfamily satisfying a desired property. Thanks to the nature of ZDDs, our algorithms offer a tool to assist users to design instances of those link puzzles. © 2012 by the authors.

DOI： 10.3390/a5020176

Scopus

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

担当区分：責任著者   記述言語：日本語   掲載種別：記事・総説・解説・論説等（学術雑誌）

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

Connected bipartite permutation graphs without vertex labels are investigated. First, the number of connected bipartite permutation graphs of n vertices is given. Based on the number, a simple algorithm that generates a connected bipartite permutation graph uniformly at random up to isomorphism is presented. Finally an enumeration algorithm of connected bipartite permutation graphs is proposed. The algorithm is based on reverse search, and it outputs each connected bipartite permutation graph in O(1) time. © 2011 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.jda.2011.11.001

Scopus

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

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

The path-distance-width of a graph measures how close the graph is to a path. We consider the problem of determining the path-distance-width for graphs with chain-like structures such as k-cocomparability graphs, AT-free graphs, and interval graphs. We first show that the problem is NP-hard even for a very restricted subclass of AT-free graphs. Next we present simple approximation algorithms with constant approximation ratios for graphs with chain-like structures. For instance, our algorithm for AT-free graphs has approximation factor 3 and runs in linear time. We also show that the problem is solvable in polynomial time for the class of cochain graphs, which is a subclass of the class of proper interval graphs. © 2011 Springer-Verlag.

DOI： 10.1007/978-3-642-25870-1_25

Scopus

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

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

For a given mountain-valley pattern of equidistant creases on a long paper strip, there are many folded states consistent with the pattern. Among these folded states, we like to fold a paper so that the number of the paper layers between each pair of hinged paper segments, which is called the crease width at the crease point, is minimized. This problem is called the stamp folding problem and there are two variants of this problem; minimization of the maximum crease width, and minimization of the total crease width. This optimization problem is recently introduced and investigated from the viewpoint of the counting problem. However, its computational complexity is not known. In this paper, we first show that the minimization problem of the maximum crease width is strongly NP-complete. Hence we cannot solve the problem in polynomial time unless P=NP. We next propose an algorithm that solves the minimization problem. The algorithm itself is a straightforward one, but its analysis is not trivial. We show that this algorithm runs in O(n 2 (n+k/k)) time where n is the number of creases and k is the total crease width. That is, the algorithm runs in O(n k+2 ) time for a constant k. Hence we can solve the problem efficiently for a small constant k. © 2011 Springer-Verlag.

DOI： 10.1007/978-3-642-22616-8_25

Scopus

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

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

Kore   Busan  

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

The Voronoi game is a two-person perfect information game modeling a competitive facility location. The original version of the game is played on a continuous domain. Only two special cases (1- dimensional case and 1-round case) have been extensively investigated. Recently, the discrete Voronoi game of which the game arena is given as a graph was introduced. In this note, we give a complete analysis of the discrete Voronoi game on a path. There are drawing strategies for both the first and the second players, except for some trivial cases. Copyright © 2011 The Institute of Electronics, Information and Communication Engineers.

DOI： 10.1587/transinf.E94.D.1185

Scopus

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

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

The graph reconstruction conjecture is a long-standing open problem in graph theory. The conjecture has been verified for all graphs with at most 11 vertices. Further, the conjecture has been verified for regular graphs, trees, disconnected graphs, unit interval graphs, separable graphs with no pendant vertex, outer-planar graphs, and unicyclic graphs. We extend the list of graph classes for which the conjecture holds. We give a proof that bipartite permutation graphs are reconstructible. © 2010 Springer-Verlag.

DOI： 10.1007/978-3-642-17461-2_29

Scopus

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

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

The graph reconstruction conjecture is a long-standing open problem in graph theory. There are many algorithmic studies related to it, such as DECK CHECKING, LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING. We study these algorithmic problems by limiting the graph class to interval graphs. Since we can solve GRAPH ISOMORPHISM for interval graphs in polynomial time, DECK CHECKING for interval graphs is easily done in polynomial time. Since the number of interval graphs that can be obtained from an interval graph by adding a vertex and edges incident to it can be exponentially large, developing polynomial time algorithms for LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING on interval graphs is not trivial. We present that these three problems are solvable in polynomial time on interval graphs. © 2010 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.tcs.2010.07.006

Scopus

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

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

Kyutacar

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

PREIMAGE CONSTRUCTION problem by Kratsch and Hemaspaandra naturally arose from the famous graph reconstruction conjecture. It deals with the algorithmic aspects of the conjecture. We present an O(n 8 ) time algorithm for PREIMAGE CONSTRUCTION on permutation graphs, where n is the number of graphs in the input. Since each graph of the input has n-1 vertices and O(n 2 ) edges, the input size is O(n 3 ). There are polynomial time isomorphism algorithms for permutation graphs. However the number of permutation graphs obtained by adding a vertex to a permutation graph is generally exponentially large. Thus exhaustive checking of these graphs does not achieve any polynomial time algorithm. Therefore reducing the number of preimage candidates is the key point. © 2010 Springer.

DOI： 10.1007/978-3-642-11440-3_12

Scopus

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

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

We investigate connected proper interval graphs without vertex labels. We first give the number of connected proper interval graphs of n vertices. Using this result, a simple algorithm that generates a connected proper interval graph uniformly at random up to isomorphism is presented. Finally an enumeration algorithm of connected proper interval graphs is proposed. The algorithm is based on reverse search, and it outputs each connected proper interval graph in O(1) time. Copyright © 2010 The Institute of Electronics, Information and Communication Engineers.

DOI： 10.1587/transinf.E93.D.1816

Scopus

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

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

USA   Hawaii  

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

The graph reconstruction conjecture is a long-standing open problem in graph theory. There are many algorithmic studies related it besides mathematical studies, such as DECK CHECKING, LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING. We study these algorithmic problems limiting the graph class to interval graphs. Since we can solve GRAPH ISOMORPHISM for interval graphs in polynomial time, DECK CHECKING for interval graphs is easily done in polynomial time. Since the number of interval graphs that can be obtained from an interval graph by adding a vertex and edges incident to it can be exponentially large, developing polynomial time algorithms for LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING on interval graphs is not trivial. We present that these three problems are solvable in polynomial time on interval graphs. © 2009 Springer Berlin Heidelberg.

DOI： 10.1007/978-3-642-02882-3_12

Scopus

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

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

Connected bipartite permutation graphs without vertex labels are investigated. First, the number of connected bipartite permutation graphs of n vertices is given. Based on the number, a simple algorithm that generates a connected bipartite permutation graph uniformly at random up to isomorphism is presented. Finally an enumeration algorithm of connected bipartite permutation graphs is proposed. The algorithm is based on the reverse search, and it outputs each connected bipartite permutation graph in time. © 2009 Springer-Verlag Berlin Heidelberg.

DOI： 10.1007/978-3-642-10631-6_111

Scopus

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

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

We investigate connected proper interval graphs without vertex labels. We first give the number of connected proper interval graphs of n vertices. Using it, a simple algorithm that generates a connected proper interval graph uniformly at random up to isomorphism is presented. Finally an enumeration algorithm of connected proper interval graphs is proposed. The algorithm is based on the reverse search, and it outputs each connected proper interval graph in O(1) time. © Springer-Verlag Berlin Heidelberg 2009.

DOI： 10.1007/978-3-642-00202-1_16

Scopus

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

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

USA   New York  

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

Korea   Gwangju  

Kyutacar

開催期間： 2022年09月22日   記述言語：日本語   開催地：オンライン   国名：日本国  

開催期間： 2022年09月22日   記述言語：日本語   開催地：オンライン   国名：日本国  

開催期間： 2022年03月24日 - 2022年03月26日   記述言語：英語   開催地：オンライン  

開催期間： 2022年03月07日 - 2022年03月08日   記述言語：日本語   開催地：オンライン  

開催期間： 2022年03月07日 - 2022年03月08日   記述言語：日本語   開催地：オンライン  

開催期間： 2022年02月01日 - 2022年02月03日   記述言語：日本語   開催地：オンライン  

開催期間： 2022年02月01日 - 2022年02月03日   記述言語：日本語   開催地：オンライン  

開催期間： 2021年02月28日 - 2021年03月02日   記述言語：英語   開催地：Yangon（オンライン）   国名：ミャンマー連邦  

開催期間： 2020年12月12日 - 2020年12月19日   記述言語：英語   開催地：オンライン  

開催期間： 2020年09月27日   記述言語：日本語   開催地：九州産業大学  

開催期間： 2020年09月19日   記述言語：日本語   開催地：オンライン  

開催期間： 2019年10月26日 - 2019年10月27日   記述言語：日本語   開催地：福岡工業大学FITセミナー  

開催期間： 2019年09月02日   記述言語：英語   開催地：岡山大学津島キャンパス  

開催期間： 2019年09月02日   記述言語：日本語   開催地：岡山大学津島キャンパス  

開催期間： 2018年12月14日   記述言語：英語   開催地：岡山大学  

開催期間： 2018年12月12日   記述言語：英語   開催地：東北大学  

開催期間： 2018年12月07日 - 2018年12月08日   記述言語：日本語   開催地：国民宿舎虹ノ松原ホテル(佐賀)  

開催期間： 2018年10月27日 - 2018年10月28日   記述言語：日本語   開催地：日本文理大学湯布院研修所  

開催期間： 2018年09月18日   記述言語：日本語   開催地：九州工業大学(飯塚キャンパス)  

開催期間： 2018年01月28日 - 2018年01月29日   記述言語：日本語   開催地：石垣島大濱信泉記念館  

開催期間： 2018年01月28日 - 2018年01月29日   記述言語：英語   開催地：石垣島大濱信泉記念館  

開催期間： 2017年12月21日   記述言語：日本語   開催地：高知工科大学  

開催期間： 2017年12月21日   記述言語：日本語   開催地：高知工科大学  

開催期間： 2017年12月21日   記述言語：日本語   開催地：高知工科大学  

開催期間： 2017年10月28日   記述言語：日本語   開催地：福岡工業大学FITセミナーハウス  

開催期間： 2017年10月28日   記述言語：日本語   開催地：福岡工業大学FITセミナーハウス  

開催期間： 2017年03月06日   記述言語：日本語   開催地：名古屋大学  

開催期間： 2017年03月06日   記述言語：日本語   開催地：名古屋大学  

開催期間： 2016年09月23日   記述言語：英語   開催地：徳島大学  

開催期間： 2016年09月06日   記述言語：英語   開催地：富山県立大学  

開催期間： 2016年06月22日 - 2016年06月23日   記述言語：英語   開催地：石川県教育会館  

開催期間： 2016年06月22日 - 2016年06月23日   記述言語：日本語   開催地：石川県教育会館  

開催期間： 2016年06月22日 - 2016年06月23日   記述言語：日本語   開催地：石川県教育会館  

開催期間： 2016年04月22日   記述言語：日本語   開催地：NAIST(奈良)  

開催期間： 2016年03月07日   記述言語：日本語   開催地：電気通信大学  

開催期間： 2016年03月07日   記述言語：日本語   開催地：電気通信大学  

開催期間： 2016年01月21日 - 2016年01月22日   記述言語：日本語   開催地：作並温泉・湯の原ホテル（宮城）  

開催期間： 2015年11月14日 - 2015年11月15日   記述言語：日本語   開催地：摂南大学  

開催期間： 2015年09月28日   記述言語：日本語   開催地：大阪大学  

開催期間： 2015年09月28日   記述言語：英語   開催地：九大西新プラザ  

開催期間： 2015年09月28日   記述言語：英語   開催地：九大西新プラザ  

開催期間： 2015年09月09日 - 2015年09月11日   記述言語：日本語   開催地：金沢大学  

開催期間： 2014年11月24日   記述言語：日本語   開催地：NAIST(奈良)  

開催期間： 2014年11月24日   記述言語：日本語   開催地：NAIST(奈良)  

開催期間： 2014年10月10日   記述言語：日本語   開催地：大阪大学  

開催期間： 2014年09月17日   記述言語：日本語   開催地：大阪大学  

開催期間： 2014年06月13日 - 2014年06月14日   記述言語：英語   開催地：道後温泉 大和屋（愛媛）  

開催期間： 2014年06月13日 - 2014年06月14日   記述言語：日本語   開催地：道後温泉 大和屋（愛媛）  

開催期間： 2014年03月17日   記述言語：日本語   開催地：東京電機大学  

開催期間： 2014年03月07日   記述言語：日本語   開催地：大阪大学  

開催期間： 2014年03月03日 - 2014年03月04日   記述言語：日本語   開催地：中央大学  

開催期間： 2014年02月18日 - 2014年02月28日   記述言語：日本語   開催地：AIST(石川)  

開催期間： 2013年11月16日 - 2013年11月17日   記述言語：日本語   開催地：大阪電気通信大学  

開催期間： 2013年11月16日 - 2013年11月17日   記述言語：日本語   開催地：大阪電気通信大学  

開催期間： 2013年11月16日 - 2013年11月17日   記述言語：日本語   開催地：大阪電気通信大学  

開催期間： 2013年11月16日 - 2013年11月17日   記述言語：日本語   開催地：大阪電気通信大学  

開催期間： 2013年05月17日 - 2013年05月18日   記述言語：日本語   開催地：小樽商科大学  

開催期間： 2013年04月24日   記述言語：日本語   開催地： 神戸大学  

開催期間： 2013年03月18日   記述言語：日本語   開催地：滋賀大学  

開催期間： 2012年12月15日 - 2012年12月16日   記述言語：日本語   開催地：ホテルマロウド軽井沢（長野）  

開催期間： 2012年12月15日 - 2012年12月16日   記述言語：日本語   開催地：ホテルマロウド軽井沢（長野）  

開催期間： 2012年06月21日   記述言語：英語   開催地：北海道大学  

開催期間： 2012年03月20日 - 2012年03月23日   記述言語：日本語   開催地：岡山大学  

開催期間： 2011年07月21日 - 2011年07月22日   記述言語：日本語   開催地：北海道大学  

開催期間： 2011年05月16日   記述言語：英語   開催地：秋田県立大学  

開催期間： 2011年03月10日   記述言語：日本語   開催地：京都大学  

開催期間： 2011年03月07日   記述言語：日本語   開催地：琉球大学  

開催期間： 2011年01月30日 - 2011年02月01日   記述言語：英語   開催地：京都大学  

開催期間： 2011年01月30日 - 2011年02月01日   記述言語：日本語   開催地：京都大学  

開催期間： 2010年11月19日   記述言語：日本語   開催地：関西大学  

開催期間： 2010年09月07日 - 2010年09月09日   記述言語：日本語   開催地：九州大学  

開催期間： 2010年07月20日   記述言語：日本語   開催地：九殿浜温泉ひみのはな（富山）  

開催期間： 2010年05月19日   記述言語：日本語   開催地：JAIST（石川）  

開催期間： 2010年03月01日   記述言語：日本語   開催地：東京工業大学  

開催期間： 2010年02月01日   記述言語：日本語   開催地：京都大学  

開催期間： 2009年09月15日   記述言語：英語   開催地：鳥取環境大学  

開催期間： 2009年09月14日   記述言語：英語   開催地：鳥取環境大学  

開催期間： 2009年07月22日 - 2009年07月24日   記述言語：日本語   開催地：かんぽの宿 松島（宮城）  

開催期間： 2008年09月29日 - 2008年09月30日   記述言語：英語   開催地：京都大学  

開催期間： 2008年07月22日 - 2008年07月24日   記述言語：日本語   開催地：国民休暇村 南紀勝浦（和歌山）  

開催期間： 2007年06月29日   記述言語：日本語   開催地：北海道大学  

開催期間： 2007年01月29日 - 2007年01月31日   記述言語：日本語   開催地：京都大学