위다레흐트 세버스티언 교수 사진

KAIST전산학부신생 랩

위다레흐트 세버스티언 연구실

위다레흐트 세버스티언 조교수 (Sebastian Wiederrecht)

랩실 소개

그래프의 어떤 구조가 문제를 다항시간에 풀 수 있게 하고, 어떤 구조가 NP-hard함을 낳는지 연구해요. 특히 minor를 제외하는 그래프류의 구조와 트리위드스 같은 특성을 살펴 독립집합 문제와 그래프 패킹 문제의 알고리즘 가능성을 탐구해요.

AI가 연구실 홈페이지를 바탕으로 쓴 소개예요

주로 내는 곳
ICALPSODADiscret. Math.

연구 내용

  • 그래프 마이너 구조: 고정 그래프를 minor로 포함하지 않는 그래프류의 구조 분석, Graph Minor Structure Theorem의 다항식 경계
  • 독립집합 문제: odd-minor-free 그래프에서 odd-cycle packing과 treewidth를 바탕으로 한 Maximum Independent Set 분석
  • 폭 매개변수 근사: 평면성의 매개변수 확장 그래프에서 branchwidth 근사
  • 패킹과 커버의 쌍대성: minor의 Erdős–Pósa 성질과 표면 그래프에서의 정수성 분석
  • 이분 그래프의 matching minor: 평평한 벽 정리와 평면 matching minor 배제
  • 그래프 패킹 알고리즘: rainbow matching을 이용한 kernelization

연구 주제별 논문

  1. 그래프 마이너와 구조 정리

  2. Erdős–Pósa 성질과 그래프 패킹

  3. 트리위드스·브랜치위드스와 계산 복잡도

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

Graph Theory · Parameterized Complexity · 전산이론

지원 가능 학과

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

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

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

비슷한 랩실 더 보기