
랩실 소개
그래프의 구조적 폭과 분해를 활용해 그래프 문제의 알고리즘과 계산 복잡도를 연구해요. 최단 경로, 근사화, 흐름 증강, 매트로이드와 제약 만족 문제까지 그래프 이론의 여러 문제를 다뤄요.
AI가 연구실 홈페이지를 바탕으로 쓴 소개예요
- 주로 내는 곳
- ACM Trans. AlgorithmsAlgorithmicaDiscret. Math. Theor. Comput. Sci.
연구 내용
- 구조적 그래프 이론: twin-width 그래프의 독립집합·지배집합·색칠 문제, twin-width의 delineation
- 그래프 분해와 논리: CMSO를 이용한 tree-like graph decomposition 변환, bounded treewidth 그래프에서 MSO2 성질의 LOCAL certification
- 매개변수 복잡도: cluster vertex deletion number로 매개변수화한 bandwidth, 불만족 제약 수를 기준으로 한 Boolean CSP의 복잡도 분류
- 흐름 증강: 유향·무향 그래프의 flow-augmentation, 가중 그래프 분리 문제
- 매트로이드와 폭 매개변수: bounded path-width 매트로이드의 인식 가능성과 정의 가능성, 실수 위 매트로이드 표현의 ∃ℝ-완전성
- 그래프 알고리즘과 근사: sparse signed tree model을 이용한 최단 경로, interval graph·split graph의 Maximum Cut 근사
연구 주제별 논문
그래프의 구조적 폭과 분해
- Twin-width VIIIa: DelineationEur. J. Comb. 2026
- CMSO-Transducing Tree-Like Graph DecompositionsSTACS 2025
- Twin-Width III: Max Independent Set, Min Dominating Set, and ColoringSIAM J. Comput. 2024
흐름 증강과 그래프 분리
- Flow-Augmentation III: Complexity Dichotomy for Boolean CSPs Parameterized by the Number of Unsatisfied ConstraintsSIAM J. Comput. 2025
- Flow-augmentation I: Directed graphsJ. ACM 2025
- Flow-augmentation II: Undirected GraphsACM Trans. Algorithms 2024
매트로이드의 폭과 표현
- Recognisability Equals Definability for Finitely Representable Matroids of Bounded Path-WidthLICS 2025
- Representing Matroids over the Reals is ∃ℝ-completeDiscret. Math. Theor. Comput. Sci. 2024
그래프 알고리즘과 근사
핵심 연구 주제
Algorithms design · Computational complexity · Structural graph theory · 전산이론
컨택 전 확인
학교 교수 페이지에서 연락처 확인교수께 첫 메일 보내는 법
미리 읽어 두면 좋은 최근 논문
- Fast Shortest Path in Graphs with Sparse Signed Tree Models and ApplicationsICALP 2026
- Twin-width VIIIa: DelineationEur. J. Comb. 2026
- A constant-factor approximation for weighted bond coverJ. Comput. Syst. Sci. 2025
지원 가능 학과
이 교수가 소속되어 있거나 겸직하는 학과·대학원이에요. 대학원 과정이 있는 곳이면 대개 그 학과로 지원해 이 교수에게 지도를 받을 수 있어요.
- 전산학부소속교수 페이지
모집 학과와 전형은 학기마다 달라져요. 지원하기 전에 학과별 입학 안내를 확인해 주세요.
2026. 11. 11. 기준으로 학과·연구실 홈페이지에서 모은 정보예요. 잘못된 정보가 있거나 내리고 싶으시면 [email protected]로 알려 주세요.
비슷한 랩실 더 보기
| 연구실 | 대학 | 대표 연구 주제 | 탑티어 논문 | 전체 논문 | 구성원 | 비교 |
|---|---|---|---|---|---|---|
윤철희 연구실윤철희 교수 | KAIST | 학습 이론·최적화AI 안전·정렬경량화·효율 AI | 29 | 29 | – | |
김도현 연구실김도현 교수 | 성균관대 | 로봇·제어 | – | – |



















