4 citations · 4 across the 3 of their papers we have counts for
6 papers · 1 filter
Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints
Yasuaki Kobayashi, Kazuhiro Kurita, Kevin Mann +2
In this paper, we consider the problems of enumerating minimal vertex covers and minimal dominating sets with capacity and/or connectivity constraints. We develop polynomial-delay…
Shortest Beer Path Queries based on Graph Decomposition
Tesshu Hanaka, Hirotaka Ono, Kunihiko Sadakane +1
Given a directed edge-weighted graph with beer vertices , a beer path between two vertices and is a path between and that visits at least o…
Independent Set Reconfiguration Parameterized by Modular-Width
Rémy Belmonte, Tesshu Hanaka, Michael Lampis +2
Independent Set Reconfiguration is one of the most well-studied problems in the setting of combinatorial reconfiguration. It is known that the problem is PSPACE-complete even for g…
Optimal Partition of a Tree with Social Distance
Masahiro Okubo, Tesshu Hanaka, Hirotaka Ono
We study the problem to find a partition of \textcolor{black}{a} graph with maximum social welfare based on social distance between vertices in , called MaxSWP. This problem…
Space-Efficient Algorithms for Longest Increasing Subsequence
Masashi Kiyomi, Hirotaka Ono, Yota Otachi +2
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 time and space. Our goa…
Minimum Certificate Dispersal with Tree Structures
Taisuke Izumi, Tomoko Izumi, Hirotaka Ono +1
Given an n-vertex graph G=(V,E) and a set R \subseteq {{x,y} | x,y \in V} of requests, we consider to assign a set of edges to each vertex in G so that for every request {u, v} in…