Caramel LabCaramel Lab
#

전화 방송 문제

1편의 한국어 분석 — 최신순으로 정렬했어요

컴퓨터 과학발표 2026.11· 5최근 1년 5회

구조적 제약 하의 전화 방송 문제

전화 방송 문제는 주어진 그래프의 특정 시작 정점에서 메시지를 모든 정점으로 전파하는 최소 라운드 수를 찾는 문제입니다. 각 라운드에서 정보를 아는 정점은 인접한 모르는 정점 하나에게 메시지를 전달할 수 있습니다. 본 연구는 이 문제의 구조적 매개변수 복잡도를 탐구합니다. 기존 연구를 확장하여, 본 연구는 전화 방송 문제가 유한한 트리 깊이를 갖는 그래프와 경로 숲에서 하나의 정점만 제거하면 되는 선인장 그래프에서도 NP-완전임을 보이며 NP-난이도 결과를 강화합니다. 이러한 난이도에 대응하여, 정점 무결성(vertex integ…

연구 트렌드로 돌아가기