Country：Japan

Award type：Award from Japanese society, conference, symposium, etc.  Country：Japan

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1007/978-981-97-0566-5_28

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/walcom/walcom2024.html#GimaKKOO24

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1587/transinf.2023fcl0003

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1587/transinf.2023fcl0002

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.tcs.2024.114507

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.4230/LIPIcs.SWAT.2024.38

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/swat/swat2024.html#OtachiST24

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1587/transinf.2023edl8067

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.tcs.2023.114158

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.dam.2023.01.026

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Other Link： https://dblp.uni-trier.de/rec/conf/aaai/2023

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

DOI： 10.1007/978-3-031-23101-8_15

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/sofsem/sofsem2023.html#KiyaOOO23

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

DOI： 10.1007/978-3-031-30448-4_19

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/ciac/ciac2023.html#HanakaOOU23

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Elsevier BV  

DOI： 10.1016/j.tcs.2022.12.007

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1137/20m1385779

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.tcs.2022.03.021

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Other Link： https://dblp.uni-trier.de/rec/conf/aaai/2022

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1007/s00224-022-10076-x

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.4230/LIPIcs.ESA.2022.61

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/esa/esa2022.html#GimaIKO22

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.4230/LIPIcs.MFCS.2022.58

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/mfcs/mfcs2022.html#ItoIKNOTW22

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.4230/LIPIcs.FUN.2022.16

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/fun/fun2022.html#ItoKMOSSUUYY22

Language：English   Publishing type：Research paper (international conference proceedings)  

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

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/walcom/walcom2022.html#EtoIKOW22

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.4230/LIPIcs.MFCS.2022.6

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/mfcs/mfcs2022.html#AbhinavBBKNOS22

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1007/s00453-022-00962-8

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1007/s00453-021-00875-y

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl - Leibniz-Zentrum für Informatik  

DOI： 10.4230/LIPIcs.ISAAC.2022.20

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/isaac/isaac2022.html#GimaO22

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1007/s00453-021-00921-9

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1007/s00224-020-09967-8

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

DOI： 10.1007/978-3-030-89543-3_29

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/cocoon/cocoon2021.html#ItoIKNOW21

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.dam.2021.07.030

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1007/s00446-021-00401-x

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.ipl.2020.106084

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

DOI： 10.1007/978-3-030-75242-2_19

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/ciac/ciac2021.html#GimaHKKO21

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

DOI： 10.1007/978-3-030-89543-3_54

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/cocoon/cocoon2021.html#KanzakiOU21

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

DOI： 10.1007/978-3-030-91081-5_40

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/sss/sss2021.html#YamauchiKO21

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.4230/LIPIcs.IPEC.2020.21

Authorship：Corresponding author   Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1007/s00453-020-00737-z

Authorship：Corresponding author   Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1007/978-3-030-60440-0_23

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.comgeo.2020.101648

Authorship：Corresponding author   Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1007/s00453-020-00700-y

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.4230/LIPIcs.ICALP.2020.67

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1007/s00453-020-00679-6

Authorship：Corresponding author   Language：English   Publishing type：Part of collection (book)   Publisher：Springer International Publishing  

DOI： 10.1007/978-3-030-48966-3_4

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.tcs.2018.08.009

Authorship：Corresponding author   Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1007/s00224-018-09908-6

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.7155/jgaa.00528

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.2197/ipsjjip.28.849

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl - Leibniz-Zentrum für Informatik  

DOI： 10.4230/LIPIcs.ESA.2020.14

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/esa/esa2020.html#Belmonte0LMO20

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：International Foundation for Autonomous Agents and Multiagent Systems  

researchmap

Other Link： https://dblp.uni-trier.de/conf/atal/2020

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

DOI： 10.1007/978-3-030-42071-0_12

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/birthday/bodlaender2020.html#Otachi20

Language：English   Publishing type：Research paper (scientific journal)  

© 2019 Elsevier Ltd In this study, we proposed combined kernel-based methods to leverage patent citation graph performance for patent classification. The concept is to use the combined graph kernels of the citation graph to classify patent documents, as a hybrid approach. A multiple kernel framework was used for integrating multiple datasets of various kernels into a combined kernel. We employed seven graph kernels as the baselines and the combination of random walks and Weisfeiler–Lehman subtree kernels to achieve higher performance. We calculated the kernel values of each patent pairwise and employed an SVM classifier to carry out the classification task. The investigation results demonstrate that the combined graph kernel outperforms single kernels.

DOI： 10.1016/j.wpi.2019.03.002

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Springer  

DOI： 10.1007/978-3-030-17402-6_8

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Springer  

DOI： 10.1007/978-3-030-30786-8_22

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.4230/LIPIcs.DISC.2019.25

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Springer  

DOI： 10.1007/978-3-030-17402-6_4

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.7155/jgaa.00486

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.comgeo.2019.01.002

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1007/s00453-018-0481-y

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.tcs.2019.02.032

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1587/transfun.E102.A.1134

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.tcs.2018.11.024

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.4230/LIPIcs.STACS.2019.13

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Springer New York LLC  

The problem MaxW-Light (MaxW-Heavy) for an undirected graph is to assign a direction to each edge so that the number of vertices of outdegree at most W (resp. at least W) is maximized. It is known that these problems are NP-hard even for fixed W. For example, Max 0-Light is equivalent to the problem of finding a maximum independent set. In this paper, we show that for any fixed constant W, MaxW-Heavy can be solved in linear time for hereditary graph classes for which treewidth is bounded by a function of degeneracy. We show that such graph classes include chordal graphs, circular-arc graphs, d-trapezoid graphs, chordal bipartite graphs, and graphs of bounded clique-width. To have a polynomial-time algorithm for MaxW-Light, we need an additional condition of a polynomial upper bound on the number of potential maximal cliques to apply the metatheorem by Fomin et al. (SIAM J Comput 44:54–87, 2015). The aforementioned graph classes, except bounded clique-width graphs, satisfy such a condition. For graphs of bounded clique-width, we present a dynamic programming approach not using the metatheorem to show that it is actually polynomial-time solvable for this graph class too. We also study the parameterized complexity of the problems and show some tractability and intractability results.

DOI： 10.1007/s00453-017-0399-9

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：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

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

A set of vertices in a graph is c-colorable if the subgraph induced by the set has a proper c-coloring. In this paper, we study the problem of finding a step-by-step transformation (reconfiguration) between two c-colorable sets in the same graph. This problem generalizes the well-studied Independent Set Reconfiguration problem. As the first step toward a systematic understanding of the complexity of this general problem, we study the problem on classes of perfect graphs. We first focus on interval graphs and give a combinatorial characterization of the distance between two c-colorable sets. This gives a linear-time algorithm for finding an actual shortest reconfiguration sequence for interval graphs. Since interval graphs are exactly the graphs that are simultaneously chordal and co-comparability, we then complement the positive result by showing that even deciding reachability is PSPACE-complete for chordal graphs and for co-comparability graphs. The hardness for chordal graphs holds even for split graphs. We also consider the case where c is a fixed constant and show that in such a case the reachability problem is polynomial-time solvable for split graphs but still PSPACE-complete for co-comparability graphs. The complexity of this case for chordal graphs remains unsettled. As by-products, our positive results give the first polynomial-time solvable cases (split graphs and interval graphs) for Feedback Vertex Set Reconfiguration.

DOI： 10.4230/LIPIcs.SWAT.2018.27

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

FIXED-FLOOD-IT and FREE-FLOOD-IT are combinatorial problems on graphs that generalize a very popular puzzle called Flood-It. Both problems consist of recoloring moves whose goal is to produce a monochromatic ("flooded") graph as quickly as possible. Their difference is that in FREE-FLOOD-IT the player has the additional freedom of choosing the vertex to play in each move. In this paper, we investigate how this freedom affects the complexity of the problem. It turns out that the freedom is bad in some sense. We show that some cases trivially solvable for FIXED-FLOOD-IT become intractable for FREE-FLOOD-IT. We also show that some tractable cases for FIXED-FLOOD-IT are still tractable for FREE-FLOOD-IT but need considerably more involved arguments. We finally present some combinatorial properties connecting or separating the two problems. In particular, we show that the length of an optimal solution for FIXED-FLOOD-IT is always at most twice that of FREE-FLOOD-IT, and this is tight.

DOI： 10.4230/LIPIcs.FUN.2018.5

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

A graph is d-orientable if its edges can be oriented so that the maximum in-degree of the resulting digraph is at most d. d-orientability is a well-studied concept with close connections to fundamental graph-theoretic notions and applications as a load balancing problem. In this paper we consider the d-Orientable Deletion problem: given a graph G = (V, E), delete the minimum number of vertices to make G d-orientable. We contribute a number of results that improve the state of the art on this problem. Specifically: We show that the problem is W[2]-hard and log n-inapproximable with respect to k, the number of deleted vertices. This closes the gap in the problem’s approximability. We completely characterize the parameterized complexity of the problem on chordal graphs: it is FPT parameterized by d + k, but W-hard for each of the parameters d, k separately. We show that, under the SETH, for all d, , the problem does not admit a (d + 2 − )tw, algorithm where tw is the graph’s treewidth, resolving as a special case an open problem on the complexity of PseudoForest Deletion. We show that the problem is W-hard parameterized by the input graph’s clique-width. Complementing this, we provide an algorithm running in time dO(d·cw), showing that the problem is FPT by d + cw, and improving the previously best know algorithm for this case.

DOI： 10.4230/LIPIcs.SWAT.2018.24

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Elsevier B.V.  

A pseudoforest is a graph where each connected component contains at most one cycle, or alternatively, a graph that can be turned into a forest by removing at most one edge from each connected component. In this paper, we show that the following problem can be solved in O(3knkO(1)) time: given a graph G and an integer k, can we delete at most k vertices from G such that we obtain a pseudoforest? The result improves upon an earlier result by Philip et al. (2015) who gave a (nonlinear) 7.56knO(1)-time algorithm both in the exponential factor depending on k as well as in the polynomial factor depending on n.

DOI： 10.1016/j.dam.2017.10.018

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

Given a sequence of integers, we want to find a longest increasing subsequence of the sequence. It is known that this problem can be solved in O(n log n) time and space. Our goal in this paper is to reduce the space consumption while keeping the time complexity small. For n = s = n, we present algorithms that use O(s log n) bits and O(1 s · n2 · log n) time for computing the length of a longest increasing subsequence, and O(1 s · n2 · log2 n) time for finding an actual subsequence. We also show that the time complexity of our algorithms is optimal up to polylogarithmic factors in the framework of sequential access algorithms with the prescribed amount of space.

DOI： 10.4230/LIPIcs.STACS.2018.44

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Springer New York LLC  

Given two graphs G and H, we say that G contains H as an induced minor if a graph isomorphic to H can be obtained from G by a sequence of vertex deletions and edge contractions. We study the complexity of Graph Isomorphism on graphs that exclude a fixed graph as an induced minor. More precisely, we determine for every graph H that Graph Isomorphism is polynomial-time solvable on H-induced-minor-free graphs or that it is GI-complete. Additionally, we classify those graphs H for which H-induced-minor-free graphs have bounded clique-width. These two results complement similar dichotomies for graphs that exclude a fixed graph as an induced subgraph, minor, or subgraph.

DOI： 10.1007/s00453-016-0234-8

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

Containing many classic optimization problems, the family of vertex deletion problems has an important position in algorithm and complexity study. The celebrated result of Lewis and Yannakakis gives a complete dichotomy of their complexity. It however has nothing to say about the case when the input graph is also special. This paper initiates a systematic study of vertex deletion problems from one subclass of chordal graphs to another. We give polynomial-time algorithms or proofs of NP-completeness for most of the problems. In particular, we show that the vertex deletion problem from chordal graphs to interval graphs is NP-complete.

DOI： 10.4230/LIPIcs.FSTTCS.2017.22

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

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

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.tcs.2018.05.039

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

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

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Springer New York LLC  

A safe set of a graph (Formula presented.) is a non-empty subset S of V such that for every component A of G[S] and every component B of (Formula presented.), we have (Formula presented.) whenever there exists an edge of G between A and B. In this paper, we show that a minimum safe set can be found in polynomial time for trees. We then further extend the result and present polynomial-time algorithms for graphs of bounded treewidth, and also for interval graphs. We also study the parameterized complexity. We show that the problem is fixed-parameter tractable when parameterized by the solution size. Furthermore, we show that this parameter lies between the tree-depth and the vertex cover number. We then conclude the paper by showing hardness for split graphs and planar graphs.

DOI： 10.1007/s10878-017-0205-2

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Information Processing Society of Japan  

Hitori is a popular “pencil-and-paper” puzzle defined as follows. In n-hitori, we are given an n×n rectangular grid in which each square is labeled with a positive integer, and the goal is to paint a subset of the squares so that the following three rules are satisfied: Rule 1) No row or column has a repeated unpainted label
Rule 2) Painted squares are never (horizontally or vertically) adjacent
Rule 3) The unpainted squares are all connected (via horizontal and vertical connections). The grid is called an instance of n-hitori if it has a unique solution. In this paper, we introduce hitori number and maximum hitori number which are defined as follows: For every integer n, hitori number h(n) is the minimum number of different integers used in an instance where the minimum is taken over all the instances of n-hitori. For every integer n, maximum hitori number h(n) is the maximum number of different integers used in an instance where the maximum is taken over all the instances of n-hitori. We then prove that ⌊(2n - 1)/3⌋ ≤ h(n) ≤ 2⌊n/3⌋ + 1 for n ≥ 2 and ⌊(4n2 - 4n + 11)/5⌋ ≥ h(n) ≤ (4n2 + 2n - 2)/5 for n ≤ 3.

DOI： 10.2197/ipsjjip.25.695

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SPRINGER  

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

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

An alliance in a graph is a set of vertices that is either safe under attacks from the neighborhood (defensive), capable of attacking its neighbors (offensive), or simultaneously defensive and offensive (powerful). An alliance is global if all nonmembers are adjacent to some members of the alliance. The concept of alliances was introduced by Kristiansen et al. (2004). After that many results concerning the complexity for finding a minimum alliance were shown. It was shown that the problem of finding a minimum alliance of any variant is NP-hard in general. For some variants, it was shown that the problem becomes polynomial time solvable when restricted to trees or series-parallel graphs.
In this paper, we show that the problems for all variants are efficiently solvable for much larger graph classes. We present a polynomial-time algorithm for graphs of bounded clique-width. We also show that the problem is fixed-parameter tractable when parameterized by the vertex cover number. (C) 2017 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2017.02.004

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SPRINGER  

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 , 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

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

A pseudoforest is a graph where each connected component contains at most one cycle, or alternatively, a graph that can be turned into a forest by removing at most one edge from each connected component. In this paper, we show that the following problem can be solved in O(3knkO(1)) time: given a graph G and an integer k, can we delete at most k vertices from G such that we obtain a pseudoforest? The result improves upon an earlier result by Philip et al. [MFCS 2015] who gave a (nonlinear) 7.56knO(1)-time algorithm both in the exponential factor depending on k as well as in the polynomial factor depending on n.

DOI： 10.4230/LIPIcs.IPEC.2016.7

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

A unit disk graph is a c-strip graph if it has a unit disk representation in which all centers of the unit disks lie between two parallel lines at distance c. The classes of c-strip graphs for various c are studied in the literature. For example, the 0-strip graphs are exactly the unit interval graphs, and every root 3/2-strip graph is a co-comparability graph. In this paper, we introduce the class of thin strip graphs and study their properties. A graph is a thin strip graph if it is a c-strip graph for every c > 0. We show that there is no constant t such that the t-strip graphs are exactly the thin strip graphs. We also show that the class of thin strip graphs properly includes the class of mixed unit interval graphs. (C) 2015 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2015.01.018

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

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. (C) 2015 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2015.05.035

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer Verlag  

In this paper, we consider the problem of listing the maximal k-degenerate induced subgraphs of a chordal graph, and propose an output-sensitive algorithm using delay O(m\\cdot \\omega (G)) for any n-vertex chordal graph with m edges, where \\omega (G) \\le n is the maximum size of a clique in G. The problem generalizes that of enumerating maximal independent sets and maximal induced forests, which correspond to respectively 0-degenerate and 1-degenerate subgraphs.

DOI： 10.1007/978-3-319-62389-4_13

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

The problem MAX W-LIGHT (MAX W-HEAVY) for an undirected graph is to assign a direction to each edge so that the number of vertices of outdegree at most W (resp. at least W) is maximized. It is known that these problems are NP-hard even for fixed W. For example, Max 0-LIGHT is equivalent to the problem of finding a maximum independent set. In this paper, we show that for any fixed constant W, MAX W-HEAVY can be solved in linear time for hereditary graph classes for which treewidth is bounded by a function of degeneracy. We show that such graph classes include chordal graphs, circular-arc graphs, d-trapezoid graphs, chordal bipartite graphs, and graphs of bounded clique-width. To have a polynomial-time algorithm for MAX W-LIGHT, we need an additional condition of a polynomial upper bound on the number of potential maximal cliques to apply the metatheorem by Fomin, Todinca, and Villanger [SIAM J. Comput., 44(1):57-87, 2015]. The aforementioned graph classes, except bounded clique-width graphs, satisfy such a condition. For graphs of bounded clique-width, we present a dynamic programming approach not using the metatheorem to show that it is actually polynomial-time solvable for this graph class too. We also study the parameterized complexity of the problems and show some tractability and intractability results.

DOI： 10.4230/LIPIcs.ISAAC.2016.20

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

In 1969, Roberts introduced proper and unit interval graphs and proved that these classes are equal. Natural generalizations of unit interval graphs called k-length interval graphs were considered in which the number of different lengths of intervals is limited by k. Even after decades of research, no insight into their structure is known and the complexity of recognition is open even for k = 2. We propose generalizations of proper interval graphs called k-nested interval graphs in which there are no chains of k + 1 intervals nested in each other. It is easy to see that k-nested interval graphs are a superclass of k-length interval graphs. We give a linear-time recognition algorithm for k-nested interval graphs. This algorithm adds a missing piece to Gajarský et al. [FOCS 2015] to show that testing FO properties on interval graphs is FPT with respect to the nesting k and the length of the formula, while the problem is W[2]-hard when parameterized just by the length of the formula. Further, we show that a generalization of recognition called partial representation extension is polynomial-time solvable for k-nested interval graphs, while it is NP-hard for k-length interval graphs, even when k = 2.

DOI： 10.4230/LIPIcs.ISAAC.2016.45

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

We present a polynomial-time algorithm for solving SUBGRAPH ISOMORPHISM where the base graphs are bipartite permutation graphs and the pattern graphs are chain graphs. (C) 2016 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.ip1.2016.04.006

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

It is proved that the total length of any set of countably many rectifiable curves, whose union meets all straight lines that intersect the unit square U, is at least 2.00002. This is the first improvement on the lower bound of 2 by Jones in 1964. A similar bound is proved for all convex sets U other than a triangle.

DOI： 10.4230/LIPIcs.SoCG.2016.46

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

Given two graphs, SUBGRAPH ISOMORPHISM is the problem of deciding whether the first graph (the base graph) contains a subgraph isomorphic to the second one (the pattern graph). This problem is NP-complete even for very restricted graph classes such as connected proper interval graphs. Only a few cases are known to be polynomial-time solvable even if we restrict the graphs to be perfect. For example, if both graphs are co-chain graphs, then the problem can be solved in linear time.
In this paper, we present a polynomial-time algorithm for the case where the base graphs are chordal graphs and the pattern graphs are co-chain graphs. We also present a linear-time algorithm for the case where the base graphs are trivially perfect graphs and the pattern graphs are threshold graphs. These results answer some of the open questions of Kijima et al. (2012). To present a complexity contrast, we then show that even if the base graphs are somewhat restricted perfect graphs, the problem of finding a pattern graph that is a chain graph, a co-chain graph, or a threshold graph is NP-complete. (C) 2015 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2015.01.040

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

Many graph parameters of grid-like graphs are studied because of their algorithmic consequences. An important concept in this context is that of treewidth. Treewidth of graphs is a graph parameter for measuring how close a graph is to a tree. In this paper, we study the treewidth of toroidal grids and show that the treewidth of the n x n toroidal grid is either 2n - 2 or 2n - 1. We then show that these bounds are tight in some cases. To show the lower bounds, we construct brambles of high orders. (C) 2015 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2015.06.027

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

We give a polynomial-time approximation scheme for the unique unit-square coverage problem: given a set of points and a set of axis-parallel unit squares, both in the plane, we wish to find a subset of squares that maximizes the number of points contained in exactly one square in the subset. Erlebach and van Leeuwen [9] introduced this problem as the geometric version of the unique coverage problem, and the best approximation ratio by van Leeuwen [21] before our work was 2. Our scheme can be generalized to the budgeted unique unit-square coverage problem, in which each point has a profit, each square has a cost, and we wish to maximize the total profit of the uniquely covered points under the condition that the total cost is at most a given bound. (C) 2015 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.comgeo.2015.10.004

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

Given two graphs G and H, we say that G contains H as an induced minor if a graph isomorphic to H can be obtained from G by a sequence of vertex deletions and edge contractions. We study the complexity of Graph Isomorphism on graphs that exclude a fixed graph as an induced minor. More precisely, we determine for every graph H that Graph Isomorphism is polynomial-time solvable on H-induced-minor-free graphs or that it is isomorphism complete. Additionally, we classify those graphs H for which H-induced-minor-free graphs have bounded clique-width. Those two results complement similar dichotomies for graphs that exclude a fixed graph as an induced subgraph, minor or subgraph.

DOI： 10.1007/978-3-662-53174-7_21

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer Verlag  

A safe set of a graph G = (V,E) is a non-empty subset S of V such that for every component A of G[S] and every component B of G[V \\ S], we have |A| ≥ |B| whenever there exists an edge of G between A and B. In this paper, we show that a minimum safe set can be found in polynomial time for trees. We then further extend the result and present polynomial-time algorithms for graphs of bounded treewidth, and also for interval graphs. We also study the parameterized complexity of the problem. We show that the problem is fixed-parameter tractable when parameterized by the solution size. Furthermore, we show that this parameter lies between tree-depth and vertex cover number.

DOI： 10.1007/978-3-319-48749-6_18

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

Suppose that we are given two independent sets I-b and I-r of a graph such that vertical bar l(b)vertical bar =vertical bar I-r vertical bar and imagine that a token is placed on each vertex in I-b. Then, the SLIDING TOKEN problem is to determine whether there exists a sequence of independent sets which transforms I-b into I-r so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. This problem is known to be PSPACE-complete even for planar graphs, and also for bounded treewidth graphs. In this paper, we thus study the problem restricted to trees, and give the following three results: (1) the decision problem is solvable in linear time; (2) for a yes-instance, we can find in quadratic time an actual sequence of independent sets between I-b and I-r whose length (i.e., the number of token-slides) is quadratic; and (3) there exists an infinite family of instances on paths for which any sequence requires quadratic length. (C) 2015 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.tcs.2015.07.037

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

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' and some pre-drawn subtrees of T'. 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' leading to vastly different problems: (i) T = T', (ii) T is a subdivision of T', (iii) T is a supergraph of T', and (iv) T' is a topological minor of T. In some cases, it is interesting to consider the complexity even when 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. 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'.
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' is limited, partial representation extension of proper interval graphs is "equivalent" to the BINPACKING problem. (C) 2015 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.tcs.2015.02.007

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG  

Secure sets and defensive alliances in graphs are studied. They are sets of vertices that are safe in some senses. In this paper, we first present a fixed-parameter algorithm for finding a small secure set, whose running time ismuch faster than the previously known one. We then present improved bound on the smallest sizes of defensive alliances and secure sets for hypercubes. These results settle some open problems paused recently.

DOI： 10.1587/transinf.2014FCP0007

Web of Science

researchmap

Other Link： http://dblp.uni-trier.de/db/journals/ieicet/ieicet98d.html#journals/ieicet/AmanoOOU15

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer Verlag  

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

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：UNIV ZIELONA GORA  

Two spanning trees T-1 and T-2 of a graph G are completely independent if, for any two vertices u and v, the paths from u to v in T-1 and T-2 are internally disjoint. For a graph G, we denote the maximum number of pairwise completely independent spanning trees by cist(G). In this paper, we consider cist(G) when G is a partial k-tree.
First we show that [k/2] <= cist(G) <= k - 1 for any k-tree G. Then we show that for any p is an element of {[k/2],..., k - 1}, there exist infinitely many k-trees G such that cist(G) = p. Finally we consider algorithmic aspects for computing cist(G). Using Courcelle's theorem, we show that there is a linear-time algorithm that computes cist(G) for a partial k-tree, where k is a fixed constant.

DOI： 10.7151/dmgt.1806

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer Verlag  

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

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

We study reconfiguration problems for cliques in a graph, which determine whether there exists a sequence of cliques that transforms a given clique into another one in a step-by-step fashion. As one step of a transformation, we consider three different types of rules, which are defined and studied in reconfiguration problems for independent sets. We first prove that all the three rules are equivalent in cliques. We then show that the problems are PSPACE-complete for perfect graphs, while we give polynomial-time algorithms for several classes of graphs, such as even-hole-free graphs and cographs. In particular, the shortest variant, which computes the shortest length of a desired sequence, can be solved in polynomial time for chordal graphs, bipartite graphs, planar graphs, and bounded treewidth graphs.

DOI： 10.1007/978-3-319-17142-5_19

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER INT PUBLISHING AG  

Sliding Token is a natural reconfiguration problem in which vertices of independent sets are iteratively replaced by neighbors. We develop techniques that may be useful in answering the conjecture that Sliding Token is polynomial-time decidable on bipartite graphs. Along the way, we give efficient algorithms for Sliding Token on bipartite permutation and bipartite distance-hereditary graphs.

DOI： 10.1007/978-3-662-48971-0_21

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

A base-monotone region with a base is a subset of the cells in a pixel grid such that if a cell is contained in the region then so are the ones on a shortest path from the cell to the base. The problem of decomposing a pixel grid into disjoint base-monotone regions was first studied in the context of image segmentation. It is known that for a given pixel grid and base-lines, one can compute in polynomial time a maximum-weight region that can be decomposed into disjoint base-monotone regions with respect to the given baselines (Chun et al., 2012 [4]). We continue this line of research and show the NP-hardness of the problem of optimally locating k base-lines in a given n x n pixel grid. We then present an O (n(3))-time 2-approximation algorithm for this problem. We also study two related problems, the k base-segment problem and the quad-decomposition problem, and present some complexity results for them. (C) 2013 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.tcs.2013.11.030

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

Network localization is important for networks with no prefixed positions of network nodes such as sensor networks. We are given a subset of the set of ((n)(2)) pairwise distances among n sensors in some Euclidean space. We want to determine the positions of each sensor from the (partial) distance information. The input can be seen as an edge weighted graph. In this paper, we present some efficient algorithms that solve this problem using the structures of input graphs, which we call their cores. For instance, we present a polynomial-time algorithm solving the network localization problem for graphs with connected dominating sets of bounded size. This algorithm allows us to have fixed-parameter tractable algorithms for some restricted instances such as graphs with connected vertex covers of bounded size. (C) 2014 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.tcs.2014.02.020

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

We give an improved approximation algorithm for the unique unit-disk coverage problem: Given a set of points and a set of unit disks, both in the plane, we wish to find a subset of disks that maximizes the number of points contained in exactly one disk in the subset. Erlebach and van Leeuwen (2008) introduced this problem as the geometric version of the unique coverage problem, and gave a polynomial-time 18-approximation algorithm. In this paper, we improve this approximation ratio 18 to 2 +4/root 3+epsilon (<4.3095+epsilon) for any fixed constant epsilon>0. Our algorithm runs in polynomial time which depends exponentially on 1/epsilon. The algorithm can be generalized to the budgeted unique unit-disk coverage problem in which each point has a profit, each disk has a cost, and we wish to maximize the total profit of the uniquely covered points under the condition that the total cost is at most a given bound. (C) 2014 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.tcs.2014.04.014

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

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.(c) 2012 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2012.11.015

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

Two lower bounds for the treewidth of product graphs are presented in terms of the bramble number. The first bound is that the bramble number of the Cartesian product of graphs G(1) and G(2) must be at least the product of the Hadwiger number of G(1) and the PI number of G(2), where the PI number is a new graph parameter introduced in this paper. The second bound is that the bramble number of the strong product of graphs G(1) and G(2) must be at least the product of the Hadwiger number of G(1) and the bramble number of G(2). We also demonstrate applications of the lower bounds. (C) 2013 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2013.08.005

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

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.

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

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

Given two graphs, Subgraph Isomorphism is the problem of deciding whether the first graph (the base graph) contains a subgraph isomorphic to the second graph (the pattern graph). This problem is NP-complete for very restricted graph classes such as connected proper interval graphs. Only a few cases are known to be polynomial-time solvable even if we restrict the graphs to be perfect. For example, if both graphs are co-chain graphs, then the problem can be solved in linear time.
In this paper, we present a polynomial-time algorithm for the case where the base graphs are chordal graphs and the pattern graphs are co-chain graphs. We also present a linear-time algorithm for the case where the base graphs are trivially perfect graphs and the pattern graphs are threshold graphs. These results answer some of the open questions of Kijima et al. [Discrete Math. 312, pp. 3164-3173, 2012]. To present a complexity contrast, we then show that even if the base graphs are somewhat restricted perfect graphs, the problem of finding a pattern graph that is a chain graph, a co-chain graph, or a threshold graph is NP-complete.

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

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

We study the parameterized complexity of the graph isomorphism problem when parameterized by width parameters related to tree decompositions. We apply the following technique to obtain fixed-parameter tractability for such parameters. We first compute an isomorphism invariant set of potential bags for a decomposition and then apply a restricted version of the Weisfeiler-Lehman algorithm to solve isomorphism. With this we show fixed-parameter tractability for several parameters and provide a unified explanation for various isomorphism results concerned with parameters related to tree decompositions.
As a possibly first step towards intractability results for parameterized graph isomorphism we develop an fpt Turing-reduction from strong tree width to the a priori unrelated parameter maximum degree.

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

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

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.

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

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

We provide algorithms performing Depth-First Search (DFS) on a directed or undirected graph with n vertices and m edges using only O(n) bits. One algorithm uses O(n) bits and runs in O(mlog n) time. Another algorithm uses n+ o(n) bits and runs in polynomial time. Furthermore, we show that DFS on a directed acyclic graph can be done in space n/2(Omega(root log n)) and in polynomial time, and we also give a simple linear-time O(log n)-space algorithm for the depth-first traversal of an undirected tree. Finally, we also show that for a graph having an O(1)-size feedback set, DFS can be done in O(log n) space. Our algorithms are based on the analysis of properties of DFS and applications of the s-t connectivity algorithms due to Reingold and Barnes et al., both of which run in sublinear space.

DOI： 10.1007/978-3-319-13075-0_44

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

Suppose that we are given two independent sets I-b and I-r of a graph such that vertical bar I-b vertical bar = vertical bar I-r vertical bar, and imagine that a token is placed on each vertex in I-b. Then, the sliding token problem is to determine whether there exists a sequence of independent sets which transforms I-b and I-r so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. This problem is known to be PSPACE-complete even for planar graphs, and also for bounded treewidth graphs. In this paper, we show that the problem is solvable for trees in quadratic time. Our proof is constructive: for a yes-instance, we can find an actual sequence of independent sets between I-b and I-r whose length (i. e., the number of token-slides) is quadratic. We note that there exists an infinite family of instances on paths for which any sequence requires quadratic length.

DOI： 10.1007/978-3-319-13075-0_31

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

The problem of decomposing a pixel grid into base-monotone regions was first studied in the context of image segmentation. It is known that for a given pixel grid and baselines, one can compute in polynomial time a maximum-weight region that can be decomposed into disjoint base-monotone regions [Chun et al. ISAAC 2009]. We continue this line of research and show the NP-hardness of the problem of optimally locating k baselines in a given n ×n pixel grid. We also present an O(n3)-time 2-approximation algorithm for this problem. We then study two related problems, the k base-segment problem and the quad-decomposition problem, and present some complexity results for them. © 2013 Springer-Verlag.

DOI： 10.1007/978-3-642-36065-7_7

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

The flooding games, which are called Flood-It, Mad Virus, or HoneyBee, are a kind of coloring games and they have been becoming popular online. In these games, each player colors one specified cell in his/her turn, and all connected neighbor cells of the same color are also colored by the color. This flooding or coloring spreads on the same color cells. It is natural to consider the coloring games on general graphs: Once a vertex is colored, the flooding flows along edges in the graph. Recently, computational complexities of the variants of the flooding games on several graph classes have been studied. We investigate the one player flooding games on some graph classes characterized by interval representations. Our results state that the number of colors is a key parameter to determine the computational complexity of the flooding games. © 2013 Springer-Verlag.

DOI： 10.1007/978-3-642-45281-9_7

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

We study the graph isomorphism problem for graph classes defined by sets of forbidden subgraphs. We show that there is a complexity dichotomy in case the set of forbidden subgraphs is finite. More precisely, we show that the problem is polynomial-time solvable if the forbidden set contains a forest of subdivided stars and is graph isomorphism complete otherwise. We also show that, assuming that the graph isomorphism problem is not polynomial-time solvable in general, there is no such dichotomy for the cases of infinite sets of forbidden subgraphs. To this end, we conditionally show that there exists a graph class closed under taking subgraphs with intermediate isomorphism problem, i.e., a class on which the isomorphism problem is neither polynomial-time solvable nor graph isomorphism complete.

DOI： 10.1007/978-3-642-45030-3_11

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：UNIV ZIELONA GORA  

The path-distance-width of a connected graph G is the minimum integer w satisfying that there is a nonempty subset of S subset of V(G) such that the number of the vertices with distance i from S is at most w for any nonnegative integer i.
In this note, we determine the path-distance-width of hypercubes.

DOI： 10.7151/dmgt.1682

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

Klavík et al. [arXiv:1207.6960] recently introduced a generalization of recognition called the bounded representation problem which we study for the classes of interval and proper interval graphs. The input gives a graph G and in addition for each vertex v two intervals ℒv and ℛv called bounds. We ask whether there exists a bounded representation in which each interval Iv has its left endpoint in ℒv and its right endpoint in . We show that the problem can be solved in linear time for interval graphs and in quadratic time for proper interval graphs. Robert's Theorem states that the classes of proper interval graphs and unit interval graphs are equal. Surprisingly, the bounded representation problem is polynomially solvable for proper interval graphs and NP-complete for unit interval graphs [Klavík et al., arxiv:1207.6960]. So unless P = NP, the proper and unit interval representations behave very differently. The bounded representation problem belongs to a wider class of restricted representation problems. These problems are generalizations of the well-understood recognition problem, and they ask whether there exists a representation of G satisfying some additional constraints. The bounded representation problems generalize many of these problems. © 2013 Springer-Verlag.

DOI： 10.1007/978-3-642-45030-3_50

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

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. (c) 2012 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disc.2012.07.010

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SPRINGER  

We study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apex-minor-free graphs, a general class of graphs containing planar graphs, graphs of bounded treewidth, and graphs of bounded genus, the problem to determine whether a given graph has spanning tree congestion at most k can be solved in linear time for every fixed k. We also show that for every fixed k and d the problem is solvable in linear time for graphs of degree at most d. In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes NP-complete for any fixed ka parts per thousand yen8. Moreover, the hardness result holds for graphs excluding the complete graph on 6 vertices as a minor. We also observe that for ka parts per thousand currency sign3 the problem becomes polynomially time solvable.

DOI： 10.1007/s00453-011-9565-7

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

This paper presents a simple algorithm to generate all ordered trees with exactly n vertices including exactly k leaves. The best known algorithm generates such trees in O(n - k) time per tree, whereas our algorithm generates such trees in O(1) time per tree in the worst case. (C) 2011 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.tcs.2011.01.017

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG  

This paper presents an efficient algorithm to generate all (unordered) rooted trees with exactly vertices including exactly k leaves. There are known results on efficient enumerations of some classes of graphs embedded on a plane, for instance, biconnected and triconnected triangulations [3], [6], and floorplans [4]. On the other hand, it is difficult to enumerate a class of graphs without a fixed embedding. The paper is on enumeration of rooted trees without a fixed embedding. We already proposed an algorithm to generate all "ordered" trees with 17 vertices including k leaves [11], while the algorithm cannot seem to efficiently generate all (unordered) rooted trees with it vertices including k leaves. We design a simple tree structure among such trees, then by traversing the tree structure we generate all such trees in constant time per tree in the worst case. By repeatedly applying the algorithm for each k = 1, 2, . . . , n - 1, we can also generate all rooted trees with exactly n vertices.

DOI： 10.1587/transinf.E95.D.763

Web of Science

researchmap

Other Link： http://dblp.uni-trier.de/db/journals/ieicet/ieicet95d.html#journals/ieicet/IshikawaYON12

Language：English   Publishing type：Research paper (scientific journal)  

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

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

We give an improved approximation algorithm for the unique unit-disk coverage problem: Given a set of points and a set of unit disks, both in the plane, we wish to find a subset of disks that maximizes the number of points contained in exactly one disk in the subset. Erlebach and van Leeuwen (2008) introduced this problem as the geometric version of the unique coverage problem, and gave a polynomial-time 18-approximation algorithm. In this paper, we improve this approximation ratio 18 to 2 + 4/root 3 + epsilon (< 4.3095 + epsilon) for any fixed constant epsilon > 0. Our algorithm runs in polynomial time which depends exponentially on 1/epsilon. The algorithm can be generalized to the budgeted unique unit-disk coverage problem in which each point has a profit, each disk has a cost, and we wish to maximize the total profit of the uniquely covered points under the condition that the total cost is at most a given bound.

DOI： 10.1007/978-3-642-35261-4_40

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

We give a polynomial-time approximation scheme for the unique unit-square coverage problem: given a set of points and a set of axis-parallel unit squares, both in the plane, we wish to find a subset of squares that maximizes the number of points contained in exactly one square in the subset. Erlebach and van Leeuwen (2008) introduced this problem as the geometric version of the unique coverage problem, and the best approximation ratio by van Leeuwen (2009) before our work was 2. Our scheme can be generalized to the budgeted unique unit-square coverage problem, in which each point has a profit, each square has a cost, and we wish to maximize the total profit of the uniquely covered points under the condition that the total cost is at most a given bound. © 2012 Springer-Verlag.

DOI： 10.1007/978-3-642-31155-0_3

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

We show that Graph Isomorphism problem (GI) can be solved in O(n(2)) time for graphs of bounded connected-path-distance-width, and more generally, in O(n(c+1)) time for graphs of bounded c-connected-path-distance-width, where n is the number of vertices. These results extend the result of Yamazaki, Bodlaender, de Fluiter, and Thilikos [Isomorphism for graphs of bounded distance width. Algorithmica 24, 105-127 (1999)], who showed the fixed-parameter tractability of GI parameterized by rooted-path-distance-width.

DOI： 10.1007/978-3-642-35261-4_48

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

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 pre-drawn subtrees, the number of components and the size of the tree T'. We describe an interesting relation with integer partition problems. The problem 3-Partition is used in the NP-completeness reductions. The BIN-PACKING problem is closely related to the extension of interval graphs when space in T' is limited, and we obtain "equivalency" with BIN PACKING.

DOI： 10.1007/978-3-642-35261-4_47

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

In 1987, Simonson conjectured that every k-outerplanar graph of maximum degree d has spanning tree congestion at most k . d [S. Simonson, A variation on the min cut linear arrangement problem, Math. Syst. Theory 20(1987)235-252]. We show that his conjecture is true and the bound is tight for outerplanar graphs and k-outerplanar graphs of maximum degree 4. We give a precise characterization of the spanning tree congestion of outerplanar graphs, and thus show that the spanning tree congestion of outerplanar graphs can be determined in linear time. (C) 2011 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disc.2011.03.002

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

We study the bandwidth and the pathwidth of multi-dimensional grids. It can be shown for grids, that these two parameters are equal to a more basic graph parameter, the vertex boundary width. Using this fact, we determine the bandwidth and the pathwidth of three-dimensional grids, which were known only for the cubic case. As a by-product, we also determine the two parameters of multi-dimensional grids with relatively large maximum factors. (C) 2011 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disc.2011.02.019

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

Spanning tree congestion is a relatively new graph parameter, which has been studied intensively. This paper studies the complexity of the problem to determine the spanning tree congestion for non-sparse graph classes, while it was investigated for some sparse graph classes before. We prove that the problem is NP-hard even for chain graphs and split graphs. To cope with the hardness of the problem, we present a fast (exponential- time) exact algorithm that runs in O*(2 n) time, where n denotes the number of vertices. Additionally, we present simple combinatorial lem- mas, which yield a constant-factor approximation algorithm for cographs, and a linear-time algorithm for chordal cographs.

DOI： 10.7155/jgaa.00246

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

Spanning tree congestion is a relatively new graph parameter, which has been studied intensively. This paper studies the complexity of the problem to determine the spanning tree congestion for non-sparse graph classes, while it was investigated for some sparse graph classes before. We prove that the problem is NP-hard even for chain graphs and split graphs. To cope with the hardness of the problem, we present a fast (exponential-time) exact algorithm that runs in O*(2(n)) time, where n denotes the number of vertices. Additionally, we provide a constant-factor approximation algorithm for cographs, and a linear-time algorithm for chordal cographs.

DOI： 10.1007/978-3-642-20877-5_44

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：University of Zielona Gora  

Let G be a connected graph and T be a spanning tree of G. For e ∈ E(T ), the congestion of e is the number of edges in G joining the two components of T - e. The congestion of T is the maximum congestion over all edges in T. The spanning tree congestion of G is the minimum congestion over all its spanning trees. In this paper, we determine the spanning tree congestion of the rook's graph Km Kn for any m and n.

DOI： 10.7151/dmgt.1577

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

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.

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

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

The carving-width of a graph is the minimum congestion of routing trees for the graph. We determine the carving-width of generalized hypercubes: Hamming graphs, even grids, and tori. Our results extend the result of Chandran and Kavitha [L.S. Chandran, T. Kavitha, The carvingwidth of hypercubes, Discrete Math. 306 (2006) 2270-2274] that determines the carving-width of hypercubes. (C) 2010 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disc.2010.06.039

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

We study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the complexity of this problem. First, we show that for every fixed k and d the problem to determine whether a given graph has spanning tree congestion at most k can be solved in linear time for graphs of degree at most d. In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes NP-complete for any fixed k >= 10. For very small values of k however, the problem becomes polynomially solvable. We also show that it is NP-hard to approximate the spanning tree congestion within a factor better than 11/10. On planar graphs, we prove the problem is NP-hard in general, but solvable in linear time for fixed k.

DOI： 10.1007/978-3-642-16926-7_3

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

Let G be a connected graph and T be a spanning tree of G. For e is an element of E(T), the congestion of e is the number of edges in G connecting two components of T - e. The edge congestion of G in T is the maximum congestion over all edges in T. The spanning tree congestion of G is the minimum congestion of G in its spanning trees. In this paper, we show the spanning tree congestion for the complete k-partite graphs and the two-dimensional tori. We also address lower bounds of spanning tree congestion for the multi-dimensional grids and the hypercubes. (C) 2008 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disc.2008.12.021

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

The security number of a graph is the cardinality of a smallest vertex subset of the graph Such that any attack on the subset is defendable. In this paper, we determine the security number of two-dimensional cylinders and tori. This result settles a conjecture of Brigham et al. [R.C. Brigham, R.D. Dutton, S.T. Hedetniemi, Security in graphs, Discrete Appl. Math. 155(2007)1708-1714]. (C) 2009 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2009.03.020

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

In this paper, we give a simple algorithm to generate all ordered trees with exactly n vertices including exactly k leaves. The best known algorithm generates such trees in O(n - k) time for each, while our algorithm generates Such trees in O(1) time for each in worst case.

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

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

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 O(1) time.

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

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

Gavril [F. Gavril, Algorithms for maximum weight induced paths, Information Processing Letters 81 (2002) 203-208] showed that the length of a longest induced path for graphs having no induced cycles on more than k vertices can be computed in O(n(k)m) time where n and m denote the number of vertices and edges, respectively. In this paper, we present an O(n(k)) time algorithm for the same problem. (C) 2008 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2008.01.019

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

The vertex boundary-width problem (for short VBWP) is to determine the value of vbw(G) = max(1 <= l <= vertical bar V vertical bar) min (S subset of V,vertical bar S vertical bar=l)vertical bar N(S)vertical bar for a given graph G = (V, E), where N(S) = {upsilon is not an element of S vertical bar upsilon is a neighbor of u for some u is an element of S}. In this paper, we give a lower bound for vertex boundary-width of complete k-ary trees. (C) 2007 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disc.2007.05.014

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

We show that the class of unit grid intersection graphs properly includes both of the classes of interval bigraphs and of P-6-free chordal bipartite graphs. We also demonstrate that the classes of unit grid intersection graphs and of chordal bipartite graphs are incomparable. (C) 2007 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2007.07.010

Web of Science

researchmap

Event date： 2020.12

Language：English   Presentation type：Oral presentation (general)  

Event date： 2020.9

Language：English   Presentation type：Oral presentation (general)  

Event date： 2020.9

Language：English   Presentation type：Oral presentation (general)  

Event date： 2020.7

Language：English   Presentation type：Oral presentation (general)  

Event date： 2020.6

Language：English   Presentation type：Oral presentation (general)  

Event date： 2020.6

Language：English   Presentation type：Oral presentation (general)  

Event date： 2020.5

Language：English   Presentation type：Oral presentation (general)