Tesshu Hanaka | DeepAI

AI Chat

Featured Co-authors

Daniel Lokshtanov
55 publications
Yusuke Kobayashi
36 publications
Yota Otachi
32 publications
Yasuaki Kobayashi
32 publications
Eun Jung Kim
29 publications
Hans L. Bodlaender
29 publications
Michael Lampis
28 publications
Takehiro Ito
25 publications
Lars Jaffke
22 publications
Uéverton S. Souza
20 publications
Kazuhiro Kurita
19 publications

∙ 07/06/2023

Shortest Beer Path Queries based on Graph Decomposition

Given a directed edge-weighted graph G=(V, E) with beer vertices B⊆ V, a...

0 Tesshu Hanaka, et al. ∙

∙ 03/02/2023

Solving Distance-constrained Labeling Problems for Small Diameter Graphs via TSP

In this paper, we give a simple polynomial-time reduction of L(p)-Labeli...

0 Tesshu Hanaka, et al. ∙

∙ 02/14/2023

Grouped Domination Parameterized by Vertex Cover, Twin Cover, and Beyond

A dominating set S of graph G is called an r-grouped dominating set if S...

0 Tesshu Hanaka, et al. ∙

∙ 11/10/2022

Winner Determination Algorithms for Graph Games with Matching Structures

Cram, Domineering, and Arc Kayles are well-studied combinatorial games. ...

0 Tesshu Hanaka, et al. ∙

∙ 07/20/2022

Computing Densest k-Subgraph with Structural Parameters

Densest k-Subgraph is the problem to find a vertex subset S of size k su...

0 Tesshu Hanaka, et al. ∙

∙ 02/14/2022

Hedonic Games and Treewidth Revisited

We revisit the complexity of the well-studied notion of Additively Separ...

0 Tesshu Hanaka, et al. ∙

∙ 01/22/2022

A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems

Finding a single best solution is the most common objective in combinato...

0 Tesshu Hanaka, et al. ∙

∙ 12/10/2021

Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study

Finding diverse solutions in combinatorial problems recently has receive...

0 Tesshu Hanaka, et al. ∙

∙ 07/07/2021

Capacitated Network Design Games on a Generalized Fair Allocation Model

The cost-sharing connection game is a variant of routing games on a netw...

0 Tesshu Hanaka, et al. ∙

∙ 01/23/2021

Exploring the Gap Between Treedepth and Vertex Cover Through Vertex Integrity

For intractable problems on graphs of bounded treewidth, two graph param...

0 Tatsuya Gima, et al. ∙

∙ 12/09/2020

An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion

A cactus is a connected graph that does not contain K_4 - e as a minor. ...

0 Yuuki Aoike, et al. ∙

∙ 09/25/2020

Finding a Maximum Minimal Separator: Graph Classes and Fixed-Parameter Tractability

We study the problem of finding a maximum cardinality minimal separator ...

0 Tesshu Hanaka, et al. ∙

∙ 09/22/2020

Computing L(p,1)-Labeling with Combined Parameters

Given a graph, an L(p,1)-labeling of the graph is an assignment f from t...

0 Tesshu Hanaka, et al. ∙

∙ 09/21/2020

(In)approximability of Maximum Minimal FVS

We study the approximability of the NP-complete Maximum Minimal Feedback...

0 Louis Dublois, et al. ∙

∙ 09/08/2020

Finding Diverse Trees, Paths, and More

Mathematical modeling is a standard approach to solve many real-world pr...

0 Tesshu Hanaka, et al. ∙

∙ 08/08/2020

Parameterized Complexity of (A,ℓ)-Path Packing

Given a graph G = (V,E), A ⊆ V, and integers k and ℓ, the (A,ℓ)-Path Pac...

0 Rémy Belmonte, et al. ∙

∙ 07/09/2020

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

The cut-set ∂(S) of a graph G=(V,E) is the set of edges that have one en...

0 Gabriel L. Duarte, et al. ∙

∙ 02/28/2020

An optimal algorithm for Bisection for bounded-treewidth graphs

The maximum/minimum bisection problems are, given an edge-weighted graph...

0 Tesshu Hanaka, et al. ∙

∙ 02/25/2020

Hedonic Seat Arrangement Problems

In this paper, we study a variant of hedonic games, called Seat Arrangem...

0 Hans L. Bodlaender, et al. ∙

∙ 08/30/2019

Computational Complexity of Hedonic Games on Sparse Graphs

The additively separable hedonic game (ASHG) is a model of coalition for...

0 Tesshu Hanaka, et al. ∙

∙ 08/09/2019

Parameterized Algorithms for Maximum Cut with Connectivity Constraints

We study two variants of Maximum Cut, which we call Connected Maximum Cu...

0 Hiroshi Eto, et al. ∙

∙ 05/25/2019

Subgraph Isomorphism on Graph Classes that Exclude a Substructure

We study Subgraph Isomorphism on graph classes defined by a fixed forbid...

0 Hans L. Bodlaender, et al. ∙

∙ 05/01/2019

Independent Set Reconfiguration Parameterized by Modular-Width

Independent Set Reconfiguration is one of the most well-studied problems...

0 Rémy Belmonte, et al. ∙

∙ 02/13/2019

New Results on Directed Edge Dominating Set

We study a family of generalizations of Edge Dominating Set on directed ...

0 Rémy Belmonte, et al. ∙

∙ 01/27/2019

Parameterized Complexity of Safe Set

In this paper we study the problem of finding a small safe set S in a gr...

0 Rémy Belmonte, et al. ∙

∙ 09/10/2018

Optimal Partition of a Tree with Social Distance

We study the problem to find a partition of graph G with maximum social ...

0 Masahiro Okubo, et al. ∙

∙ 07/30/2018

Parameterized Orientable Deletion

A graph is d-orientable if its edges can be oriented so that the maximum...

0 Tesshu Hanaka, et al. ∙

∙ 03/16/2018

Reconfiguring spanning and induced subgraphs

Subgraph reconfiguration is a family of problems focusing on the reachab...

0 Tesshu Hanaka, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world