Shin-ichi Tanigawa

activity

20062026

most citedInfinitesimal Rigidity of Symmetric Frameworks

10 citations · 48 across the 37 of their papers we have counts for

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2022

Nearly Tight Spectral Sparsification of Directed Hypergraphs by a Simple Iterative Sampling Algorithm

Kazusato Oko, Shinsaku Sakaue, Shin-ichi Tanigawa

Spectral hypergraph sparsification, an attempt to extend well-known spectral graph sparsification to hypergraphs, has been extensively studied over the past few years. For undirect…

cs.DS2015★ 2 cited

Improved Approximation Algorithms for k-Submodular Function Maximization

Satoru Iwata, Shin-ichi Tanigawa, Yuichi Yoshida

This paper presents a polynomial-time $1/2$ -approximation algorithm for maximizing nonnegative $k$ -submodular functions. This improves upon the previous $max {1/3, 1/ (1 + a)}$ -appr…

cs.DS2011★ 1 cited

Constant-Time Algorithms for Sparsity Matroids

Hiro Ito, Shin-ichi Tanigawa, Yuichi Yoshida

A graph $G = (V, E)$ is called $(k, ℓ)$ -full if $G$ contains a subgraph $H = (V, F)$ of $k ∣ V ∣ - ℓ$ edges such that, for any non-empty $F^{'} \subseteq F$ , $∣ F^{'} ∣ \leq k ∣ V (F^{'}) ∣ - ℓ$ hol…