Yu Nakahata

activity

20182025

most citedDecomposing a Graph into Unigraphs

3 citations · 6 across the 6 of their papers we have counts for

collaborators

Showing 2020Show all

2 papers · 1 filter

cs.DS2020

A Note on Exponential-Time Algorithms for Linearwidth

Yasuaki Kobayashi, Yu Nakahata

In this note, we give an algorithm that computes the linearwidth of input $n$ -vertex graphs in time $O^{*} (2^{n})$ , which improves a trivial $O^{*} (2^{m})$ -time algorithm, where $n$ and $m…

cs.CG2020★ 2 cited

Compiling Crossing-free Geometric Graphs with Connectivity Constraint for Fast Enumeration, Random Sampling, and Optimization

Yu Nakahata, Takashi Horiyama, Shin-ichi Minato +1

Given $n$ points in the plane, we propose algorithms to compile connected crossing-free geometric graphs into directed acyclic graphs (DAGs). The DAGs allow efficient counting, enu…