Jungho Ahn (안정호)

Preprints

Approximating maximum cut on interval graphs and split graphs beyond Goemans-Williamson
-with Ian DeHaan, Eun Jung Kim, and Euiwoong Lee.

Finding d-cuts in claw-free graphs
-with Tala Eagling-Vose, Felicia Lucke, Daniël Paulusma, and Siani Smith.
-arXiv:2505.17993

Twin-width one
-with Hugo Jacob, Noleen Köhler, Christophe Paul, Amadeus Reinald, and Sebastian Wiederrecht.
-arXiv:2501.00991

A coarse Erdős-Pósa theorem
-with Pascal Gollin, Tony Huynh, and O-joung Kwon.
-arXiv:2407.05883

Spectral integral variation of signed graphs
-with Cheolwon Heo and Sunyo Moon.
-arxiv:2401.02639

Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
-with Jinha Kim and O-joung Kwon.
-arXiv:2207.06660

Accepted Journal Papers

Jungho Ahn, Seonghyuk Im, and Sang-il Oum, The proper conflict-free k-coloring problem and the odd k-coloring problem are NP-complete on bipartite graphs, Discrete Appl. Math. (2025).
-DOI:10.1016/j.dam.2025.06.026

Jungho Ahn, Debsoumya Chakraborti, Kevin Hendrey, and Sang-il Oum, Twin-width of subdivisions of multigraphs, SIAM J. Discrete Math. (2025).
-DOI:10.1137/23M1621514

Jungho Ahn, Debsoumya Chakraborti, Kevin Hendrey, Donggyu Kim, and Sang-il Oum, Twin-width of random graphs, Random Structures & Algorithms (2024).
-DOI:10.1002/rsa.21247

Jungho Ahn, Eduard Eiben, O-joung Kwon, and Sang-il Oum, A polynomial kernel for 3-leaf power deletion. Algorithmica (2023).
-DOI:10.1007/s00453-023-01129-9

Jungho Ahn, Kevin Hendrey, Donggyu Kim, and Sang-il Oum, Bounds for the twin-width of graphs. SIAM J. Discrete Math. (2022).
-DOI:10.1137/21M1452834

Jungho Ahn, Lars Jaffke, O-joung Kwon, and Paloma T. Lima. Well-partitioned chordal graphs. Discrete Math. (2022).
-DOI:10.1016/j.disc.2022.112985

Jungho Ahn, Eun Jung Kim, and Euiwoong Lee. Towards constant-factor approximation for chordal/distance-hereditary vertex deletion. Algorithmica (2022).
-DOI:10.1007/s00453-022-00963-7

Refereed Conference Papers

Approximating maximum cut on interval and split graphs beyond Goemans-Williamson
-with Ian DeHaan, Eun Jung Kim, and Euiwoong Lee.
-accepted in APPROX 2025, Aug. 11-13, Berkeley, United States.

Twin-width one
-with Hugo Jacob, Noleen Köhler, Christophe Paul, Amadeus Reinald, and Sebastian Wiederrecht.
-accepted in STACS 2025, Mar. 4-7, Jena, Germany.
-arXiv:2501.00991 / DOI:10.4230/LIPIcs.STACS.2025.6

A coarse Erdős-Pósa theorem
-with Pascal Gollin, Tony Huynh, and O-joung Kwon.
-accepted in SODA25, Jan. 12-15, New Orleans, United States.
-arXiv:2407.05883 / DOI:10.1137/1.9781611978322

Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
-with Jinha Kim and O-joung Kwon.
-accepted in ISAAC 2023, Dec. 3-6, Kyoto, Japan.
-arXiv:2207.06660 / DOI:10.4230/LIPIcs.ISAAC.2023.5

Three problems on well-partitioned chordal graphs
-with Lars Jaffke, O-joung Kwon, and Paloma T. Lima.
-accepted in CIAC 2021, May 10-12, Larnaca, Cyprus.
-DOI:10.1007/978-3-030-60440-0_12

Towards constant-factor approximation for chordal / distance-hereditary vertex deletion
-with Eun Jung Kim and Euiwoong Lee.
-accepted in ISAAC 2020, Dec. 14-18, Hong Kong.
-arXiv:2009.00809 / DOI:10.4230/LIPIcs.ISAAC.2020.62

A polynomial kernel for 3-leaf power deletion
-with Eduard Eiben, O-joung Kwon, and Sang-il Oum.
-accepted in MFCS 2020, Aug. 24-28, Prague, Czech Republic.
-arXiv:1911.04249 / DOI:10.4230/LIPIcs.MFCS.2020.5

Well-partitioned chordal graphs: obstruction set and disjoint paths
-with Lars Jaffke, O-joung Kwon, and Paloma T. Lima.
-accepted in WG 2020, June 24-26, Leeds, United Kingdom.
-arXiv:2002.10859 / DOI:10.1007/978-3-030-60440-0_12