Search

Your search keyword '"ETO, HIROSHI"' showing total 381 results
Start Over Author "ETO, HIROSHI"
381 results on '"ETO, HIROSHI"'

1. Directed Path Partition Problem on Directed Acyclic Graphs

Author

Eto, Hiroshi, Kawaharada, Shunsuke, Lin, Guohui, Miyano, Eiji, Ozdemir, Tugce, Goos, Gerhard, Series Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Rescigno, Adele Anna, editor, and Vaccaro, Ugo, editor

Published
2024
Full Text
View/download PDF

3. Reconfiguration of Regular Induced Subgraphs

Author

Eto, Hiroshi, Ito, Takehiro, Kobayashi, Yasuaki, Otachi, Yota, and Wasa, Kunihiro

Subjects
Computer Science - Data Structures and Algorithms
Abstract

We study the problem of checking the existence of a step-by-step transformation of $d$-regular induced subgraphs in a graph, where $d \ge 0$ and each step in the transformation must follow a fixed reconfiguration rule. Our problem for $d=0$ is equivalent to \textsc{Independent Set Reconfiguration}, which is one of the most well-studied reconfiguration problems. In this paper, we systematically investigate the complexity of the problem, in particular, on chordal graphs and bipartite graphs. Our results give interesting contrasts to known ones for \textsc{Independent Set Reconfiguration}., Comment: 13 pages, WALCOM 2022

Published
2021

4. Independent Set Under a Change Constraint from an Initial Solution

Author

Asahiro, Yuichi, Eto, Hiroshi, Korenaga, Kana, Lin, Guohui, Miyano, Eiji, Nonoue, Reo, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, and Mavronicolas, Marios, editor

Published
2023
Full Text
View/download PDF

5. Reconfiguration of Vertex-Disjoint Shortest Paths on Graphs

Author

Saito, Rin, Eto, Hiroshi, Ito, Takehiro, Uehara, Ryuhei, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Lin, Chun-Cheng, editor, Lin, Bertrand M. T., editor, and Liotta, Giuseppe, editor

Published
2023
Full Text
View/download PDF

6. Computing the Largest Bond and the Maximum Connected Cut of a Graph

Author

Duarte, Gabriel L., Eto, Hiroshi, Hanaka, Tesshu, Kobayashi, Yasuaki, Kobayashi, Yusuke, Lokshtanov, Daniel, Pedrosa, Lehilton L. C., Schouery, Rafael C. S., and Souza, Uéverton S.

Subjects
Computer Science - Data Structures and Algorithms, Computer Science - Computational Complexity, Computer Science - Discrete Mathematics
Abstract

The cut-set $\partial(S)$ of a graph $G=(V,E)$ is the set of edges that have one endpoint in $S\subset V$ and the other endpoint in $V\setminus S$, and whenever $G[S]$ is connected, the cut $[S,V\setminus S]$ of $G$ is called a connected cut. A bond of a graph $G$ is an inclusion-wise minimal disconnecting set of $G$, i.e., bonds are cut-sets that determine cuts $[S,V\setminus S]$ of $G$ such that $G[S]$ and $G[V\setminus S]$ are both connected. Contrasting with a large number of studies related to maximum cuts, there exist very few results regarding the largest bond of general graphs. In this paper, we aim to reduce this gap on the complexity of computing the largest bond, and the maximum connected cut of a graph. Although cuts and bonds are similar, we remark that computing the largest bond and the maximum connected cut of a graph tends to be harder than computing its maximum cut. We show that it does not exist a constant-factor approximation algorithm to compute the largest bond, unless P = NP. Also, we show that {\sc Largest Bond} and {\sc Maximum Connected Cut} are NP-hard even for planar bipartite graphs, whereas \textsc{Maximum Cut} is trivial on bipartite graphs and polynomial-time solvable on planar graphs. In addition, we show that {\sc Largest Bond} and {\sc Maximum Connected Cut} are NP-hard on split graphs, and restricted to graphs of clique-width $w$ they can not be solved in time $f(w)\times n^{o(w)}$ unless the Exponential Time Hypothesis fails, but they can be solved in time $f(w)\times n^{O(w)}$. Finally, we show that both problems are fixed-parameter tractable when parameterized by the size of the solution, the treewidth, and the twin-cover number., Comment: This paper resulted from a merge of two papers submitted to arXiv (arXiv:1908.03389 and arXiv:1910.01071). Both preliminary versions were presented at the 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Published
2020

7. Parameterized Algorithms for Maximum Cut with Connectivity Constraints

Author

Eto, Hiroshi, Hanaka, Tesshu, Kobayashi, Yasuaki, and Kobayashi, Yusuke

Subjects
Computer Science - Data Structures and Algorithms
Abstract

We study two variants of \textsc{Maximum Cut}, which we call \textsc{Connected Maximum Cut} and \textsc{Maximum Minimal Cut}, in this paper. In these problems, given an unweighted graph, the goal is to compute a maximum cut satisfying some connectivity requirements. Both problems are known to be NP-complete even on planar graphs whereas \textsc{Maximum Cut} on planar graphs is solvable in polynomial time. We first show that these problems are NP-complete even on planar bipartite graphs and split graphs. Then we give parameterized algorithms using graph parameters such as clique-width, tree-width, and twin-cover number. Finally, we obtain FPT algorithms with respect to the solution size.

Published
2019

9. Happy Set Problem on Subclasses of Co-comparability Graphs

Author

Eto, Hiroshi, Ito, Takehiro, Miyano, Eiji, Suzuki, Akira, Tamura, Yuma, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Mutzel, Petra, editor, Rahman, Md. Saidur, editor, and Slamin, editor

Published
2022
Full Text
View/download PDF

10. Reconfiguration of Regular Induced Subgraphs

Author

Eto, Hiroshi, Ito, Takehiro, Kobayashi, Yasuaki, Otachi, Yota, Wasa, Kunihiro, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Mutzel, Petra, editor, Rahman, Md. Saidur, editor, and Slamin, editor

Published
2022
Full Text
View/download PDF

12. Graph Classes and Approximability of the Happy Set Problem

Author

Asahiro, Yuichi, Eto, Hiroshi, Hanaka, Tesshu, Lin, Guohui, Miyano, Eiji, Terabaru, Ippei, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Kim, Donghyun, editor, Uma, R. N., editor, Cai, Zhipeng, editor, and Lee, Dong Hoon, editor

Published
2020
Full Text
View/download PDF

13. Parameterized Algorithms for the Happy Set Problem

Author

Asahiro, Yuichi, Eto, Hiroshi, Hanaka, Tesshu, Lin, Guohui, Miyano, Eiji, Terabaru, Ippei, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Rahman, M. Sohel, editor, Sadakane, Kunihiko, editor, and Sung, Wing-Kin, editor

Published
2020
Full Text
View/download PDF

19. Approximation Algorithm for the Distance-3 Independent Set Problem on Cubic Graphs

Author

Eto, Hiroshi, Ito, Takehiro, Liu, Zhilong, Miyano, Eiji, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Poon, Sheung-Hung, editor, Rahman, Md. Saidur, editor, and Yen, Hsu-Chun, editor

Published
2017
Full Text
View/download PDF

20. Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs

Author

Eto, Hiroshi, Ito, Takehiro, Liu, Zhilong, Miyano, Eiji, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Chan, T-H. Hubert, editor, Li, Minming, editor, and Wang, Lusheng, editor

Published
2016
Full Text
View/download PDF

21. Approximation Algorithms for the Longest Run Subsequence Problem

Author

Asahiro, Yuichi, Eto, Hiroshi, Gong, Mingyang, Jansson, Jesper, Lin, Guohui, Miyano, Eiji, Ono, Hirotaka, Tanaka, Shunichi, Asahiro, Yuichi, Eto, Hiroshi, Gong, Mingyang, Jansson, Jesper, Lin, Guohui, Miyano, Eiji, Ono, Hirotaka, and Tanaka, Shunichi

Abstract

We study the approximability of the Longest Run Subsequence problem (LRS for short). For a string S = s_1 ? s_n over an alphabet ?, a run of a symbol ? ? ? in S is a maximal substring of consecutive occurrences of ?. A run subsequence S' of S is a sequence in which every symbol ? ? ? occurs in at most one run. Given a string S, the goal of LRS is to find a longest run subsequence S^* of S such that the length |S^*| is maximized over all the run subsequences of S. It is known that LRS is APX-hard even if each symbol has at most two occurrences in the input string, and that LRS admits a polynomial-time k-approximation algorithm if the number of occurrences of every symbol in the input string is bounded by k. In this paper, we design a polynomial-time (k+1)/2-approximation algorithm for LRS under the k-occurrence constraint on input strings. For the case k = 2, we further improve the approximation ratio from 3/2 to 4/3.

Published
2023
Full Text
View/download PDF

22. Complexity of Finding Maximum Regular Induced Subgraphs with Prescribed Degree

Author

Asahiro, Yuichi, Eto, Hiroshi, Ito, Takehiro, Miyano, Eiji, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Gąsieniec, Leszek, editor, and Wolter, Frank, editor

Published
2013
Full Text
View/download PDF

23. Distance-d Independent Set Problems for Bipartite and Chordal Graphs

Author

Eto, Hiroshi, Guo, Fengrui, Miyano, Eiji, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Lin, Guohui, editor

Published
2012
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results