Source author record

Toshimasa Ishii

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

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

Posimodular Function Optimization

Given a posimodular function $f: 2^V \to \mathbb{R}$ on a finite set $V$ , we consider the problem of finding a nonempty subset $X$ of $V$ that minimizes $f(X)$ . Posimodular functions often arise in combinatorial optimization such as undirected cut functions. In this paper, we show that any algorithm for the problem requires $Ω(2^{\frac{n}{7.54}})$ oracle calls to $f$ , where $n=|V|$ . It contrasts to the fact that the submodular function minimization, which is another generalization of cut functions, is polynomially solvable. When the range of a given posimodular function is restricted to be $D=\{0,1,...,d\}$ for some nonnegative integer $d$ , we show that $Ω(2^{\frac{d}{15.08}})$ oracle calls are necessary, while we propose an $O(n^dT_f+n^{2d+1})$ -time algorithm for the problem. Here, $T_f$ denotes the time needed to evaluate the function value $f(X)$ for a given $X \subseteq V$ . We also consider the problem of maximizing a given posimodular function. We show that $Ω(2^{n-1})$ oracle calls are necessary for solving the problem, and that the problem has time complexity $Θ(n^{d-1}T_f)$ when $D=\{0,1,..., d\}$ is the range of $f$ for some constant $d$ .

preprint2013arXiv

(Total) Vector Domination for Graphs with Bounded Branchwidth

Given a graph $G=(V,E)$ of order $n$ and an $n$ -dimensional non-negative vector $d=(d(1),d(2),\ldots,d(n))$ , called demand vector, the vector domination (resp., total vector domination) is the problem of finding a minimum $S\subseteq V$ such that every vertex $v$ in $V\setminus S$ (resp., in $V$ ) has at least $d(v)$ neighbors in $S$ . The (total) vector domination is a generalization of many dominating set type problems, e.g., the dominating set problem, the $k$ -tuple dominating set problem (this $k$ is different from the solution size), and so on, and its approximability and inapproximability have been studied under this general framework. In this paper, we show that a (total) vector domination of graphs with bounded branchwidth can be solved in polynomial time. This implies that the problem is polynomially solvable also for graphs with bounded treewidth. Consequently, the (total) vector domination problem for a planar graph is subexponential fixed-parameter tractable with respectto $k$ , where $k$ is the size of solution.

preprint2010arXiv

A linear time algorithm for L(2,1)-labeling of trees

An L(2,1)-labeling of a graph $G$ is an assignment $f$ from the vertex set $V(G)$ to the set of nonnegative integers such that $|f(x)-f(y)|\ge 2$ if $x$ and $y$ are adjacent and $|f(x)-f(y)|\ge 1$ if $x$ and $y$ are at distance 2, for all $x$ and $y$ in $V(G)$ . A $k$ -L(2,1)-labeling is an assignment $f:V(G)\to\{0,..., k\}$ , and the L(2,1)-labeling problem asks the minimum $k$ , which we denote by $λ(G)$ , among all possible assignments. It is known that this problem is NP-hard even for graphs of treewidth 2, and tree is one of a very few classes for which the problem is polynomially solvable. The running time of the best known algorithm for trees had been $\mO(Δ^{4.5} n)$ for more than a decade, however, an $\mO(n^{1.75})$-time algorithm has been proposed recently, which substantially improved the previous one, where $Δ$ is the maximum degree of $T$ and $n=|V(T)|$ . In this paper, we finally establish a linear time algorithm for L(2,1)-labeling of trees.

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.