13 Search Results for "Ono, Hirotaka"

Document
DOI: 10.4230/LIPIcs.ISAAC.2024.53
A Fast Algorithm for Computing a Planar Support for Non-Piercing Rectangles

Authors: Ambar Pal, Rajiv Raman, Saurabh Ray, and Karamjeet Singh

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
For a hypergraph ℋ = (X,ℰ) a support is a graph G on X such that for each E ∈ ℰ, the induced subgraph of G on the elements in E is connected. If G is planar, we call it a planar support. A set of axis parallel rectangles ℛ forms a non-piercing family if for any R₁, R₂ ∈ ℛ, R₁⧵R₂ is connected. Given a set P of n points in ℝ² and a set ℛ of m non-piercing axis-aligned rectangles, we give an algorithm for computing a planar support for the hypergraph (P,ℛ) in O(nlog² n + (n+m)log m) time, where each R ∈ ℛ defines a hyperedge consisting of all points of P contained in R.
Cite as

Ambar Pal, Rajiv Raman, Saurabh Ray, and Karamjeet Singh. A Fast Algorithm for Computing a Planar Support for Non-Piercing Rectangles. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 53:1-53:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{pal_et_al:LIPIcs.ISAAC.2024.53,
  author =	{Pal, Ambar and Raman, Rajiv and Ray, Saurabh and Singh, Karamjeet},
  title =	{{A Fast Algorithm for Computing a Planar Support for Non-Piercing Rectangles}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{53:1--53:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.53},
  URN =		{urn:nbn:de:0030-drops-221819},
  doi =		{10.4230/LIPIcs.ISAAC.2024.53},
  annote =	{Keywords: Algorithms, Hypergraphs, Computational Geometry, Visualization}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.14
Bounding the Treewidth of Outer k-Planar Graphs via Triangulations

Authors: Oksana Firman, Grzegorz Gutowski, Myroslav Kryven, Yuto Okada, and Alexander Wolff

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
The treewidth is a structural parameter that measures the tree-likeness of a graph. Many algorithmic and combinatorial results are expressed in terms of the treewidth. In this paper, we study the treewidth of outer k-planar graphs, that is, graphs that admit a straight-line drawing where all the vertices lie on a circle, and every edge is crossed by at most k other edges. Wood and Telle [New York J. Math., 2007] showed that every outer k-planar graph has treewidth at most 3k + 11 using so-called planar decompositions, and later, Auer et al. [Algorithmica, 2016] proved that the treewidth of outer 1-planar graphs is at most 3, which is tight. In this paper, we improve the general upper bound to 1.5k + 2 and give a tight bound of 4 for k = 2. We also establish a lower bound: we show that, for every even k, there is an outer k-planar graph with treewidth k+2. Our new bound immediately implies a better bound on the cop number, which answers an open question of Durocher et al. [GD 2023] in the affirmative. Our treewidth bound relies on a new and simple triangulation method for outer k-planar graphs that yields few crossings with graph edges per edge of the triangulation. Our method also enables us to obtain a tight upper bound of k + 2 for the separation number of outer k-planar graphs, improving an upper bound of 2k + 3 by Chaplick et al. [GD 2017]. We also consider outer min-k-planar graphs, a generalization of outer k-planar graphs, where we achieve smaller improvements.
Cite as

Oksana Firman, Grzegorz Gutowski, Myroslav Kryven, Yuto Okada, and Alexander Wolff. Bounding the Treewidth of Outer k-Planar Graphs via Triangulations. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{firman_et_al:LIPIcs.GD.2024.14,
  author =	{Firman, Oksana and Gutowski, Grzegorz and Kryven, Myroslav and Okada, Yuto and Wolff, Alexander},
  title =	{{Bounding the Treewidth of Outer k-Planar Graphs via Triangulations}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.14},
  URN =		{urn:nbn:de:0030-drops-212988},
  doi =		{10.4230/LIPIcs.GD.2024.14},
  annote =	{Keywords: treewidth, outerplanar graphs, outer k-planar graphs, outer min-k-planar graphs, cop number, separation number}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2024.2
Indexing Graphs for Shortest Beer Path Queries

Authors: David Coudert, Andrea D'Ascenzo, and Mattia D'Emidio

Published in: OASIcs, Volume 123, 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)

Abstract
A beer graph is an edge-weighted graph G = (V,E,ω) with beer vertices B ⊆ V. A beer path between two vertices s and t of a beer graph is a path that connects s and t and visits at least one vertex in B. The beer distance between two vertices is the weight of a shortest beer path, i.e. a beer path having minimum total weight. A graph indexing scheme is a two-phase method that constructs an index data structure by a one-time preprocessing of an input graph and then exploits it to compute (or accelerate the computation of) answers to queries on structures of the graph dataset. In the last decade, such indexing schemes have been designed to perform, effectively, many relevant types of queries, e.g. on reachability, and have gained significant popularity in essentially all data-intensive application domains where large number of queries have to be routinely answered (e.g. journey planners), since they have been shown, through many experimental studies, to offer extremely low query times at the price of limited preprocessing time and space overheads. In this paper, we showcase that an indexing scheme, to efficiently execute queries on beer distances or shortest beer paths for pairs of vertices of a beer graph, can be obtained by adapting the highway labeling, a recently introduced indexing method to accelerate the computation of classical shortest paths. We design a preprocessing algorithm to build a whl index, i.e. a weighted highway labeling of a beer graph, and show how it can be queried to compute beer distances and shortest beer paths. Through extensive experimentation on real networks, we empirically demonstrate its practical effectiveness and superiority, in terms of offered trade-off between preprocessing time, space overhead and query time, with respect to the state-of-the-art.
Cite as

David Coudert, Andrea D'Ascenzo, and Mattia D'Emidio. Indexing Graphs for Shortest Beer Path Queries. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 2:1-2:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{coudert_et_al:OASIcs.ATMOS.2024.2,
  author =	{Coudert, David and D'Ascenzo, Andrea and D'Emidio, Mattia},
  title =	{{Indexing Graphs for Shortest Beer Path Queries}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{2:1--2:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-350-8},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{123},
  editor =	{Bouman, Paul C. and Kontogiannis, Spyros C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2024.2},
  URN =		{urn:nbn:de:0030-drops-211907},
  doi =		{10.4230/OASIcs.ATMOS.2024.2},
  annote =	{Keywords: Graph Algorithms, Indexing Schemes, Beer Distances, Algorithms Engineering}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.97
Engineering Edge Orientation Algorithms

Authors: Henrik Reinstädtler, Christian Schulz, and Bora Uçar

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
Given an undirected graph G, the edge orientation problem asks for assigning a direction to each edge to convert G into a directed graph. The aim is to minimize the maximum out-degree of a vertex in the resulting directed graph. This problem, which is solvable in polynomial time, arises in many applications. An ongoing challenge in edge orientation algorithms is their scalability, particularly in handling large-scale networks with millions or billions of edges efficiently. We propose a novel algorithmic framework based on finding and manipulating simple paths to face this challenge. Our framework is based on an existing algorithm and allows many algorithmic choices. By carefully exploring these choices and engineering the underlying algorithms, we obtain an implementation which is more efficient and scalable than the current state-of-the-art. Our experiments demonstrate significant performance improvements compared to state-of-the-art solvers. On average our algorithm is 6.59 times faster when compared to the state-of-the-art.
Cite as

Henrik Reinstädtler, Christian Schulz, and Bora Uçar. Engineering Edge Orientation Algorithms. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 97:1-97:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{reinstadtler_et_al:LIPIcs.ESA.2024.97,
  author =	{Reinst\"{a}dtler, Henrik and Schulz, Christian and U\c{c}ar, Bora},
  title =	{{Engineering Edge Orientation Algorithms}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{97:1--97:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.97},
  URN =		{urn:nbn:de:0030-drops-211682},
  doi =		{10.4230/LIPIcs.ESA.2024.97},
  annote =	{Keywords: edge orientation, pseudoarboricity, graph algorithms}
}
Document
DOI: 10.4230/LIPIcs.CPM.2024.27
Finding Diverse Strings and Longest Common Subsequences in a Graph

Authors: Yuto Shida, Giulia Punzi, Yasuaki Kobayashi, Takeaki Uno, and Hiroki Arimura

Published in: LIPIcs, Volume 296, 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024)

Abstract
In this paper, we study for the first time the Diverse Longest Common Subsequences (LCSs) problem under Hamming distance. Given a set of a constant number of input strings, the problem asks to decide if there exists some subset X of K longest common subsequences whose diversity is no less than a specified threshold Δ, where we consider two types of diversities of a set X of strings of equal length: the Sum diversity and the Min diversity defined as the sum and the minimum of the pairwise Hamming distance between any two strings in X, respectively. We analyze the computational complexity of the respective problems with Sum- and Min-diversity measures, called the Max-Sum and Max-Min Diverse LCSs, respectively, considering both approximation algorithms and parameterized complexity. Our results are summarized as follows. When K is bounded, both problems are polynomial time solvable. In contrast, when K is unbounded, both problems become NP-hard, while Max-Sum Diverse LCSs problem admits a PTAS. Furthermore, we analyze the parameterized complexity of both problems with combinations of parameters K and r, where r is the length of the candidate strings to be selected. Importantly, all positive results above are proven in a more general setting, where an input is an edge-labeled directed acyclic graph (DAG) that succinctly represents a set of strings of the same length. Negative results are proven in the setting where an input is explicitly given as a set of strings. The latter results are equipped with an encoding such a set as the longest common subsequences of a specific input string set.
Cite as

Yuto Shida, Giulia Punzi, Yasuaki Kobayashi, Takeaki Uno, and Hiroki Arimura. Finding Diverse Strings and Longest Common Subsequences in a Graph. In 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 296, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{shida_et_al:LIPIcs.CPM.2024.27,
  author =	{Shida, Yuto and Punzi, Giulia and Kobayashi, Yasuaki and Uno, Takeaki and Arimura, Hiroki},
  title =	{{Finding Diverse Strings and Longest Common Subsequences in a Graph}},
  booktitle =	{35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024)},
  pages =	{27:1--27:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-326-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{296},
  editor =	{Inenaga, Shunsuke and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2024.27},
  URN =		{urn:nbn:de:0030-drops-201370},
  doi =		{10.4230/LIPIcs.CPM.2024.27},
  annote =	{Keywords: Sequence analysis, longest common subsequence, Hamming distance, dispersion, approximation algorithms, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.37
Shortest Beer Path Queries Based on Graph Decomposition

Authors: Tesshu Hanaka, Hirotaka Ono, Kunihiko Sadakane, and Kosuke Sugiyama

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
Given a directed edge-weighted graph G = (V, E) with beer vertices B ⊆ V, a beer path between two vertices u and v is a path between u and v that visits at least one beer vertex in B, and the beer distance between two vertices is the shortest length of beer paths. We consider indexing problems on beer paths, that is, a graph is given a priori, and we construct some data structures (called indexes) for the graph. Then later, we are given two vertices, and we find the beer distance or beer path between them using the data structure. For such a scheme, efficient algorithms using indexes for the beer distance and beer path queries have been proposed for outerplanar graphs and interval graphs. For example, Bacic et al. (2021) present indexes with size O(n) for outerplanar graphs and an algorithm using them that answers the beer distance between given two vertices in O(α(n)) time, where α(⋅) is the inverse Ackermann function; the performance is shown to be optimal. This paper proposes indexing data structures and algorithms for beer path queries on general graphs based on two types of graph decomposition: the tree decomposition and the triconnected component decomposition. We propose indexes with size O(m+nr²) based on the triconnected component decomposition, where r is the size of the largest triconnected component. For a given query u,v ∈ V, our algorithm using the indexes can output the beer distance in query time O(α(m)). In particular, our indexing data structures and algorithms achieve the optimal performance (the space and the query time) for series-parallel graphs, which is a wider class of outerplanar graphs.
Cite as

Tesshu Hanaka, Hirotaka Ono, Kunihiko Sadakane, and Kosuke Sugiyama. Shortest Beer Path Queries Based on Graph Decomposition. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{hanaka_et_al:LIPIcs.ISAAC.2023.37,
  author =	{Hanaka, Tesshu and Ono, Hirotaka and Sadakane, Kunihiko and Sugiyama, Kosuke},
  title =	{{Shortest Beer Path Queries Based on Graph Decomposition}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{37:1--37:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.37},
  URN =		{urn:nbn:de:0030-drops-193397},
  doi =		{10.4230/LIPIcs.ISAAC.2023.37},
  annote =	{Keywords: graph algorithm, shortest path problem, SPQR tree}
}
Document
DOI: 10.4230/LIPIcs.CPM.2023.2
Approximation Algorithms for the Longest Run Subsequence Problem

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

Published in: LIPIcs, Volume 259, 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)

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.
Cite as

Yuichi Asahiro, Hiroshi Eto, Mingyang Gong, Jesper Jansson, Guohui Lin, Eiji Miyano, Hirotaka Ono, and Shunichi Tanaka. Approximation Algorithms for the Longest Run Subsequence Problem. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{asahiro_et_al:LIPIcs.CPM.2023.2,
  author =	{Asahiro, Yuichi and Eto, Hiroshi and Gong, Mingyang and Jansson, Jesper and Lin, Guohui and Miyano, Eiji and Ono, Hirotaka and Tanaka, Shunichi},
  title =	{{Approximation Algorithms for the Longest Run Subsequence Problem}},
  booktitle =	{34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)},
  pages =	{2:1--2:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-276-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{259},
  editor =	{Bulteau, Laurent and Lipt\'{a}k, Zsuzsanna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.2},
  URN =		{urn:nbn:de:0030-drops-179560},
  doi =		{10.4230/LIPIcs.CPM.2023.2},
  annote =	{Keywords: Longest run subsequence problem, bounded occurrence, approximation algorithm}
}
Document
DOI: 10.4230/LIPIcs.CPM.2022.15
Polynomial-Time Equivalences and Refined Algorithms for Longest Common Subsequence Variants

Authors: Yuichi Asahiro, Jesper Jansson, Guohui Lin, Eiji Miyano, Hirotaka Ono, and Tadatoshi Utashima

Published in: LIPIcs, Volume 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)

Abstract
The problem of computing the longest common subsequence of two sequences (LCS for short) is a classical and fundamental problem in computer science. In this paper, we study four variants of LCS: the Repetition-Bounded Longest Common Subsequence problem (RBLCS) [Yuichi Asahiro et al., 2020], the Multiset-Restricted Common Subsequence problem (MRCS) [Radu Stefan Mincu and Alexandru Popa, 2018], the Two-Side-Filled Longest Common Subsequence problem (2FLCS), and the One-Side-Filled Longest Common Subsequence problem (1FLCS) [Mauro Castelli et al., 2017; Mauro Castelli et al., 2019]. Although the original LCS can be solved in polynomial time, all these four variants are known to be NP-hard. Recently, an exact, O(1.44225ⁿ)-time, dynamic programming (DP)-based algorithm for RBLCS was proposed [Yuichi Asahiro et al., 2020], where the two input sequences have lengths n and poly(n). We first establish that each of MRCS, 1FLCS, and 2FLCS is polynomially equivalent to RBLCS. Then, we design a refined DP-based algorithm for RBLCS that runs in O(1.41422ⁿ) time, which implies that MRCS, 1FLCS, and 2FLCS can also be solved in O(1.41422ⁿ) time. Finally, we give a polynomial-time 2-approximation algorithm for 2FLCS.
Cite as

Yuichi Asahiro, Jesper Jansson, Guohui Lin, Eiji Miyano, Hirotaka Ono, and Tadatoshi Utashima. Polynomial-Time Equivalences and Refined Algorithms for Longest Common Subsequence Variants. In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 223, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{asahiro_et_al:LIPIcs.CPM.2022.15,
  author =	{Asahiro, Yuichi and Jansson, Jesper and Lin, Guohui and Miyano, Eiji and Ono, Hirotaka and Utashima, Tadatoshi},
  title =	{{Polynomial-Time Equivalences and Refined Algorithms for Longest Common Subsequence Variants}},
  booktitle =	{33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)},
  pages =	{15:1--15:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-234-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{223},
  editor =	{Bannai, Hideo and Holub, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.15},
  URN =		{urn:nbn:de:0030-drops-161424},
  doi =		{10.4230/LIPIcs.CPM.2022.15},
  annote =	{Keywords: Repetition-bounded longest common subsequence problem, multiset restricted longest common subsequence problem, one-side-filled longest common subsequence problem, two-side-filled longest common subsequence problem, exact algorithms, and approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.44
Space-Efficient Algorithms for Longest Increasing Subsequence

Authors: Masashi Kiyomi, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, and Jun Tarui

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
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 sqrt(n) <= s <= n, we present algorithms that use O(s log n) bits and O(1/s n^2 log n) time for computing the length of a longest increasing subsequence, and O(1/s n^2 log^2 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.
Cite as

Masashi Kiyomi, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, and Jun Tarui. Space-Efficient Algorithms for Longest Increasing Subsequence. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kiyomi_et_al:LIPIcs.STACS.2018.44,
  author =	{Kiyomi, Masashi and Ono, Hirotaka and Otachi, Yota and Schweitzer, Pascal and Tarui, Jun},
  title =	{{Space-Efficient Algorithms for Longest Increasing Subsequence}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{44:1--44:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.44},
  URN =		{urn:nbn:de:0030-drops-84911},
  doi =		{10.4230/LIPIcs.STACS.2018.44},
  annote =	{Keywords: longest increasing subsequence, patience sorting, space-efficient algorithm}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.45
On Directed Covering and Domination Problems

Authors: Tesshu Hanaka, Naomi Nishimura, and Hirotaka Ono

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
In this paper, we study covering and domination problems on directed graphs. Although undirected Vertex Cover and Edge Dominating Set are well-studied classical graph problems, the directed versions have not been studied much due to the lack of clear definitions. We give natural definitions for Directed r-In (Out) Vertex Cover and Directed (p,q)-Edge Dominating Set as directed generations of Vertex Cover and Edge Dominating Set. For these problems, we show that (1) Directed r-In (Out) Vertex Cover and Directed (p,q)-Edge Dominating Set are NP-complete on planar directed acyclic graphs except when r=1 or (p,q)=(0,0), (2) if r>=2, Directed r-In (Out) Vertex Cover is W[2]-hard and (c*ln k)-inapproximable on directed acyclic graphs, (3) if either p or q is greater than 1, Directed (p,q)-Edge Dominating Set is W[2]-hard and (c*ln k)-inapproximable on directed acyclic graphs, (4) all problems can be solved in polynomial time on trees, and (5) Directed (0,1),(1,0),(1,1)-Edge Dominating Set are fixed-parameter tractable in general graphs. The first result implies that (directed) r-Dominating Set on directed line graphs is NP-complete even if r=1.
Cite as

Tesshu Hanaka, Naomi Nishimura, and Hirotaka Ono. On Directed Covering and Domination Problems. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 45:1-45:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{hanaka_et_al:LIPIcs.ISAAC.2017.45,
  author =	{Hanaka, Tesshu and Nishimura, Naomi and Ono, Hirotaka},
  title =	{{On  Directed Covering and Domination Problems}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{45:1--45:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.45},
  URN =		{urn:nbn:de:0030-drops-82460},
  doi =		{10.4230/LIPIcs.ISAAC.2017.45},
  annote =	{Keywords: directed graph, vertex cover, dominating set, edge dominating set, fixed-parameter algorithms}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.46
Settlement Fund Circulation Problem

Authors: Hitoshi Hayakawa, Toshimasa Ishii, Hirotaka Ono, and Yushi Uno

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
In the economic activities, the central bank has an important role to cover payments of banks, when they are short of funds to clear their debts. For this purpose, the central bank timely puts funds so that the economic activities go smooth. Since payments in this mechanism are processed sequentially, the total amount of funds put by the central bank critically depends on the order of the payments. Then an interest goes to the amount to prepare if the order of the payments can be controlled by the central bank, or if it is determined under the worst case scenario. This motivates us to introduce a brand-new problem, which we call the settlement fund circulation problem. The problems are formulated as follows: Let G=(V,A) be a directed multigraph with a vertex set V and an arc set A. Each arc a\in A is endowed debt d(a)\ge 0, and the debts are settled sequentially under a sequence \pi of arcs. Each vertex v\in V is put fund in the amount of p_{\pi}(v)\ge 0 under the sequence. The minimum/maximum settlement fund circulation problem (Min-SFC/Max-SFC) in a given graph G with debts d: A\rightarrow \mathbb{R}_{+}\cup \{0\} asks to find a bijection \pi:A\to \{1,2,\dots,|A|\} that minimizes/maximizes the total funds \sum _{v\in V}p_{\pi }(v). In this paper, we show that both Min-SFC and Max-SFC are NP-hard; in particular, Min-SFC is (I) strongly NP-hard even if G is (i) a multigraph with |V|=2 or (ii) a simple graph with treewidth at most two,and is (II) (not necessarily strongly) NP-hard for simple trees of diameter four, while it is solvable in polynomial time for stars. Also, we identify several polynomial time solvable cases for both problems.
Cite as

Hitoshi Hayakawa, Toshimasa Ishii, Hirotaka Ono, and Yushi Uno. Settlement Fund Circulation Problem. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 46:1-46:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{hayakawa_et_al:LIPIcs.ISAAC.2017.46,
  author =	{Hayakawa, Hitoshi and Ishii, Toshimasa and Ono, Hirotaka and Uno, Yushi},
  title =	{{Settlement Fund Circulation Problem}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{46:1--46:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.46},
  URN =		{urn:nbn:de:0030-drops-82351},
  doi =		{10.4230/LIPIcs.ISAAC.2017.46},
  annote =	{Keywords: Fund settlement, Algorithm, Digraph, Scheduling}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2016.7
A Faster Parameterized Algorithm for Pseudoforest Deletion

Authors: Hans L. Bodlaender, Hirotaka Ono, and Yota Otachi

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)

Abstract
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(3^k n k^{O(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.56^k n^{O(1)}-time algorithm both in the exponential factor depending on k as well as in the polynomial factor depending on n.
Cite as

Hans L. Bodlaender, Hirotaka Ono, and Yota Otachi. A Faster Parameterized Algorithm for Pseudoforest Deletion. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 7:1-7:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bodlaender_et_al:LIPIcs.IPEC.2016.7,
  author =	{Bodlaender, Hans L. and Ono, Hirotaka and Otachi, Yota},
  title =	{{A Faster Parameterized Algorithm for Pseudoforest Deletion}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{7:1--7:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.7},
  URN =		{urn:nbn:de:0030-drops-69246},
  doi =		{10.4230/LIPIcs.IPEC.2016.7},
  annote =	{Keywords: pseudoforest deletion, graph class, width parameter, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.20
Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity

Authors: Hans L. Bodlaender, Hirotaka Ono, and Yota Otachi

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
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.
Cite as

Hans L. Bodlaender, Hirotaka Ono, and Yota Otachi. Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 20:1-20:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bodlaender_et_al:LIPIcs.ISAAC.2016.20,
  author =	{Bodlaender, Hans L. and Ono, Hirotaka and Otachi, Yota},
  title =	{{Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{20:1--20:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.20},
  URN =		{urn:nbn:de:0030-drops-67898},
  doi =		{10.4230/LIPIcs.ISAAC.2016.20},
  annote =	{Keywords: orientation, graph class, width parameter, parameterized complexity}
}
  • Refine by Author
  • 8 Ono, Hirotaka
  • 3 Otachi, Yota
  • 2 Asahiro, Yuichi
  • 2 Bodlaender, Hans L.
  • 2 Hanaka, Tesshu
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 3 parameterized complexity
  • 2 graph class
  • 2 width parameter
  • 1 Algorithm
  • 1 Algorithms
  • Show More...

  • Refine by Type
  • 13 document

  • Refine by Publication Year
  • 5 2024
  • 3 2017
  • 2 2023
  • 1 2016
  • 1 2018
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact