3 citations · 12 across the 26 of their papers we have counts for
7 papers · 1 filter
Detecting and Enumerating Small Induced Subgraphs in -Closed Graphs
Tomohiro Koana, André Nichterlein
Fox et al. [SIAM J. Comp. 2020] introduced a new parameter, called -closure, for a parameterized study of clique enumeration problems. A graph is -closed if every pair of…
Computing Dense and Sparse Subgraphs of Weakly Closed Graphs
Tomohiro Koana, Christian Komusiewicz, Frank Sommer
A graph is weakly -closed if every induced subgraph of contains one vertex such that for each non-neighbor of it holds that . The weak clo…
Parameterized Complexity of Min-Power Asymmetric Connectivity
Matthias Bentert, Roman Haag, Christian Hofer +2
We investigate parameterized algorithms for the NP-hard problem Min-Power Asymmetric Connectivity (MinPAC) that has applications in wireless sensor networks. Given a directed arc-w…
Exploiting -Closure in Kernelization Algorithms for Graph Problems
Tomohiro Koana, Christian Komusiewicz, Frank Sommer
A graph is c-closed if every pair of vertices with at least c common neighbors is adjacent. The c-closure of a graph G is the smallest number such that G is c-closed. Fox et al. [I…
Parameterized Algorithms for Matrix Completion With Radius Constraints
Tomohiro Koana, Vincent Froese, Rolf Niedermeier
Considering matrices with missing entries, we study NP-hard matrix completion problems where the resulting completed matrix shall have limited (local) radius. In the pure radius ve…
The Complexity of Binary Matrix Completion Under Diameter Constraints
Tomohiro Koana, Vincent Froese, Rolf Niedermeier
We thoroughly study a novel but basic combinatorial matrix completion problem: Given a binary incomplete matrix, fill in the missing entries so that every pair of rows in the resul…
Parameterized Complexity of Geodetic Set
Leon Kellerhals, Tomohiro Koana
A vertex set of a graph is geodetic if every vertex of lies on a shortest path between two vertices in . Given a graph and , the NP-hard Geodeti…