Source author record

Hisao Tamaki

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms

Catalog footprint

Research overview

3works

1topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Heuristic computation of exact treewidth

We are interested in computing the treewidth $\tw(G)$ of a given graph $G$ . Our approach is to design heuristic algorithms for computing a sequence of improving upper bounds and a sequence of improving lower bounds, which would hopefully converge to $\tw(G)$ from both sides. The upper bound algorithm extends and simplifies Tamaki's unpublished work on a heuristic use of the dynamic programming algorithm for deciding treewidth due to Bouchitté and Todinca. The lower bound algorithm is based on the well-known fact that, for every minor $H$ of $G$ , we have $\tw(H) \leq \tw(G)$. Starting from a greedily computed minor $H_0$ of $G$ , the algorithm tries to construct a sequence of minors $H_0$ , $H_1$ , \ldots $H_k$ with $\tw(H_i) < \tw(H_{i + 1})$ for $0 \leq i < k$ and hopefully $\tw(H_k) = \tw(G)$. We have implemented a treewidth solver based on this approach and have evaluated it on the bonus instances from the exact treewidth track of PACE 2017 algorithm implementation challenge. The results show that our approach is extremely effective in tackling instances that are hard for conventional solvers. Our solver has an additional advantage over conventional ones in that it attaches a compact certificate to the lower bound it computes.

preprint2015arXiv

A faster fixed parameter algorithm for two-layer crossing minimization

We give an algorithm that decides whether the bipartite crossing number of a given graph is at most $k$ . The running time of the algorithm is upper bounded by $2^{O(k)} + n^{O(1)}$ , where $n$ is the number of vertices of the input graph, which improves the previously known algorithm due to Kobayashi et al. (TCS 2014) that runs in $2^{O(k \log k)} + n^{O(1)}$ time. This result is based on a combinatorial upper bound on the number of two-layer drawings of a connected bipartite graph with a bounded crossing number.

preprint2015arXiv

On the pathwidth of almost semicomplete digraphs

We call a digraph {\em $h$ -semicomplete} if each vertex of the digraph has at most $h$ non-neighbors, where a non-neighbor of a vertex $v$ is a vertex $u \neq v$ such that there is no edge between $u$ and $v$ in either direction. This notion generalizes that of semicomplete digraphs which are $0$ -semicomplete and tournaments which are semicomplete and have no anti-parallel pairs of edges. Our results in this paper are as follows. (1) We give an algorithm which, given an $h$ -semicomplete digraph $G$ on $n$ vertices and a positive integer $k$ , in $(h + 2k + 1)^{2k} n^{O(1)}$ time either constructs a path-decomposition of $G$ of width at most $k$ or concludes correctly that the pathwidth of $G$ is larger than $k$ . (2) We show that there is a function $f(k, h)$ such that every $h$ -semicomplete digraph of pathwidth at least $f(k, h)$ has a semicomplete subgraph of pathwidth at least $k$ . One consequence of these results is that the problem of deciding if a fixed digraph $H$ is topologically contained in a given $h$ -semicomplete digraph $G$ admits a polynomial-time algorithm for fixed $h$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.