5 citations · 9 across the 8 of their papers we have counts for
9 papers · 1 filter
Fast and Practical Single-Exponential Algorithms for Branchwidth
Taiki Kaneda, Yasuaki Kobayashi, Hisao Tamaki
In this paper, we present exact exponential algorithms for computing branchwidth that are fast both in theory and in practice. The running times of these algorithms are single-expo…
A polynomial delay algorithm generating all potential maximal cliques in triconnected planar graphs
Alexander Grigoriev, Yasuaki Kobayashi, Hisao Tamaki +1
We develop a new characterization of potential maximal cliques of a triconnected planar graph and, using this characterization, give a polynomial delay algorithm generating all pot…
A contraction-recursive algorithm for treewidth
Hisao Tamaki
Let tw(G) denote the treewidth of graph G. Given a graph G and a positive integer k such that tw(G) <= k + 1, we are to decide if tw(G) <= k. We give a certifying algorithm RTW ("R…
Heuristic computation of exact treewidth
Hisao Tamaki
We are interested in computing the treewidth $\tw(G)$ of a given graph . Our approach is to design heuristic algorithms for computing a sequence of improving upper bounds and a…
A heuristic for listing almost-clique minimal separators of a graph
Hisao Tamaki
Bodlaender and Koster (Discrete Mathematics 2006) introduced the notion of almost-clique separators in the context of computing the treewidth $\tw(G)$ of a given graph . A separ…
A heuristic use of dynamic programming to upperbound treewidth
Hisao Tamaki
For a graph , let denote the set of all potential maximal cliques of . For each subset of , let $\tw(G, Π)$ denote the smallest such that there is a tree…
Positive-instance driven dynamic programming for treewidth
Hisao Tamaki
Consider a dynamic programming scheme for a decision problem in which all subproblems involved are also decision problems. An implementation of such a scheme is {\em positive-insta…
A faster fixed parameter algorithm for two-layer crossing minimization
Yasuaki Kobayashi, Hisao Tamaki
We give an algorithm that decides whether the bipartite crossing number of a given graph is at most . The running time of the algorithm is upper bounded by …
On the pathwidth of almost semicomplete digraphs
Kenta Kitsunai, Yasuaki Kobayashi, Hisao Tamaki
We call a digraph {\em -semicomplete} if each vertex of the digraph has at most non-neighbors, where a non-neighbor of a vertex is a vertex such that there is…