10 papers
Directed Low Diameter Decomposition for Structured Digraphs
Shinwoo An, Arnold Filtser
Low diameter decompositions, or LDDs for short, are a fundamental primitive in the design of efficient graph algorithms. Roughly speaking, an LDD is a distribution over partitions…
Single-Source Shortest Path Problem in Weighted Disk Graphs
Shinwoo An, Eunjin Oh, Jie Xue
In this paper, we present efficient algorithms for the single-source shortest path problem in weighted disk graphs. A disk graph is the intersection graph of a family of disks in t…
Dynamic parameterized problems on unit disk graphs
Shinwoo An, Kyungjin Cho, Leo Jang +6
In this paper, we study fundamental parameterized problems such as -Path/Cycle, Vertex Cover, Triangle Hitting Set, Feedback Vertex Set, and Cycle Packing for dynamic unit disk…
Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs
Shinwoo An, Yeonsu Chang, Kyungjin Cho +4
Horiyama et al. (AAAI 2024) considered the problem of generating instances with a unique minimum vertex cover under certain conditions. The Minimum Pre-assignment for Uniquificatio…
Sparse Outerstring Graphs Have Logarithmic Treewidth
Shinwoo An, Eunjin Oh, Jie Xue
An outerstring graph is the intersection graph of curves lying inside a disk with one endpoint on the boundary of the disk. We show that an outerstring graph with vertices has…
ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
Shinwoo An, Eunjin Oh
In this paper, we consider the Cycle Packing problem on unit disk graphs defined as follows. Given a unit disk graph G with n vertices and an integer k, the goal is to find a set o…
Faster Algorithms for Cycle Hitting Problems on Disk Graphs
Shinwoo An, Kyungjin Cho, Eunjin Oh
In this paper, we consider three hitting problems on a disk intersection graph: Triangle Hitting Set, Feedback Vertex Set, and Odd Cycle Transversal. Given a disk intersection grap…
Feedback Vertex Set on Geometric Intersection Graphs
Shinwoo An, Eunjin Oh
In this paper, we present an algorithm for computing a feedback vertex set of a unit disk graph of size , if it exists, which runs in time , where and…
Reachability Problems for Transmission Graphs
Shinwoo An, Eunjin Oh
Let be a set of points in the plane where each point of is associated with a radius .The transmission graph of is defined as the directed graph…
EEMC: Embedding Enhanced Multi-tag Classification
Yanlin Li, Shi An, Ruisheng Zhang
The recently occurred representation learning make an attractive performance in NLP and complex network, it is becoming a fundamental technology in machine learning and data mining…