Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

<p>We are given a set <i>S</i> of <i>n</i> points in the Euclidean plane. We assume that <i>S</i> is in general position. A simple polygon <i>P</i> is an <i>empty polygon</i> of <i>S</i> if each vertex of <i>P</i> is a point in <i>S</i> and every point in <i>S</i> is either outside <i>P</i> or a vertex of <i>P</i>. In this paper, we consider the problem of enumerating all the empty polygons of a given point set. To design an efficient enumeration algorithm, we use a reverse search by Avis and Fukuda with child lists. We propose an algorithm that enumerates all the empty polygons of <i>S</i> in <i>O</i>(<i>n</i>²|<i>ε</i>(<i>S</i>)|)-time, where <i>ε</i>(<i>S</i>) is the set of empty polygons of <i>S</i>. Moreover, by applying the same idea to the problem of enumerating surrounding polygons of a given point set <i>S</i>, we propose an enumeration algorithm that enumerates them in <i>O</i>(<i>n</i>²)-delay, while the known algorithm enumerates in <i>O</i>(<i>n</i>² log <i>n</i>)-delay, where a <i>surroundingpolygon</i> of <i>S</i> is a polygon such that each vertex of the polygon is a point in <i>S</i> and every point in <i>S</i> is either inside the polygon or a vertex of the polygon.</p>

DOI： 10.1587/transfun.2022dmp0007

Scopus

CiNii Research

Publisher：Leibniz International Proceedings in Informatics, LIPIcs  

Finding a maximum cardinality common independent set in two matroids (also known as Matroid Intersection) is a classical combinatorial optimization problem, which generalizes several well-known problems, such as finding a maximum bipartite matching, a maximum colorful forest, and an arborescence in directed graphs. Enumerating all maximal common independent sets in two (or more) matroids is a classical enumeration problem. In this paper, we address an “intersection” of these problems: Given two matroids and a threshold τ, the goal is to enumerate all maximal common independent sets in the matroids with cardinality at least τ. We show that this problem can be solved in polynomial delay and polynomial space. We also discuss how to enumerate all maximal common independent sets of two matroids in non-increasing order of their cardinalities.

DOI： 10.4230/LIPIcs.MFCS.2023.58

Scopus

Publisher：Leibniz International Proceedings in Informatics, LIPIcs  

LZ-End is a variant of the well-known Lempel-Ziv parsing family such that each phrase of the parsing has a previous occurrence, with the additional constraint that the previous occurrence must end at the end of a previous phrase. LZ-End was initially proposed as a greedy parsing, where each phrase is determined greedily from left to right, as the longest factor that satisfies the above constraint [Kreft & Navarro, 2010]. In this work, we consider an optimal LZ-End parsing that has the minimum number of phrases in such parsings. We show that a decision version of computing the optimal LZ-End parsing is NP-complete by showing a reduction from the vertex cover problem. Moreover, we give a MAX-SAT formulation for the optimal LZ-End parsing adapting an approach for computing various NP-hard repetitiveness measures recently presented by [Bannai et al., 2022]. We also consider the approximation ratio of the size of greedy LZ-End parsing to the size of the optimal LZ-End parsing, and give a lower bound of the ratio which asymptotically approaches 2.

DOI： 10.4230/LIPIcs.CPM.2023.3

Scopus

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

Publisher：Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022  

Finding diverse solutions in combinatorial problems recently has received considerable attention (Baste et al. 2020; Fomin et al. 2020; Hanaka et al. 2021). In this paper we study the following type of problems: given an integer k, the problem asks for k solutions such that the sum of pairwise (weighted) Hamming distances between these solutions is maximized. Such solutions are called diverse solutions. We present a polynomial-time algorithm for finding diverse shortest stpaths in weighted directed graphs. Moreover, we study the diverse version of other classical combinatorial problems such as diverse weighted matroid bases, diverse weighted arborescences, and diverse bipartite matchings. We show that these problems can be solved in polynomial time as well. To evaluate the practical performance of our algorithm for finding diverse shortest st-paths, we conduct a computational experiment with synthetic and real-world instances. The experiment shows that our algorithm successfully computes diverse solutions within reasonable computational time.

Scopus

Event date： 2023.1 - 2023.2

Language：English   Presentation type：Oral presentation (general)  

Venue：京都大学   Country：Japan  

Event date： 2023.1 - 2023.2

Language：English   Presentation type：Oral presentation (general)  

Country：Japan  

Event date： 2022.6

Language：English   Presentation type：Public lecture, seminar, tutorial, course, or other speech  

Event date： 2022.3

Language：Japanese   Presentation type：Oral presentation (invited, special)  

Venue：オンライン開催   Country：Japan