김은정 교수 사진

KAIST전산학부

김은정 연구실

김은정 부교수 (Eun Jung Kim)

랩실 소개

그래프의 구조적 폭과 분해를 활용해 그래프 문제의 알고리즘과 계산 복잡도를 연구해요. 최단 경로, 근사화, 흐름 증강, 매트로이드와 제약 만족 문제까지 그래프 이론의 여러 문제를 다뤄요.

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 근사

연구 주제별 논문

  1. 그래프의 구조적 폭과 분해

  2. 흐름 증강과 그래프 분리

  3. 매트로이드의 폭과 표현

  4. 그래프 알고리즘과 근사

연구실 홈페이지에서 소개 읽기
핵심 연구 주제

Algorithms design · Computational complexity · Structural graph theory · 전산이론

지원 가능 학과

이 교수가 소속되어 있거나 겸직하는 학과·대학원이에요. 대학원 과정이 있는 곳이면 대개 그 학과로 지원해 이 교수에게 지도를 받을 수 있어요.

모집 학과와 전형은 학기마다 달라져요. 지원하기 전에 학과별 입학 안내를 확인해 주세요.

2026. 11. 11. 기준으로 학과·연구실 홈페이지에서 모은 정보예요. 잘못된 정보가 있거나 내리고 싶으시면 [email protected]로 알려 주세요.

비슷한 랩실 더 보기

  • KAIST 윤철희 교수

    탑티어 29논문 29구성원 –

    학습 이론·최적화AI 안전·정렬
  • 성균관대 김도현 교수

    구성원 –

    로봇·제어