태그 보관물: parameterized-complexity

parameterized-complexity

FPT 축소 기술에 대한 언급이 있습니까? Garey와 Johnson의 유명한

모두가 알다시피, Garey와 Johnson의 유명한 저서 (및 다른 많은 책들)는 고전적인 환경에서 축소 기술에 대한 훌륭한 참고 자료를 제공합니다. fpt 축소와 같이 매개 변수화 된 알고리즘의 축소 기술 주제에 대한 조사 나 서적이 있습니까?



답변

원래 두 다우니 및 휄로우에 의해 매개 변수화 복잡성 책 , 그리고 Flum 및 그로 헤에 의한 새로운 책은 , 감소 기술에 대한 좋은 참조입니다.


답변

알고리즘 설계 기법은 종종 축소에도 도움이됩니다. 따라서 FPT 알고리즘을 설계하는 데 사용되는 기술에 대해 배우는 것이 좋을 수 있는데, 고정 매개 변수 및 정확한 알고리즘 (2009) 관한 Spring School 의 노트가 출발점이 될 수 있습니다. 특히 다음과 같은 훌륭한 개요 대화를 볼 수 있습니다.

  • FPT 알고리즘 기법 에 관한 Dániel Marx ( 슬라이드 ).
  • Thore Husfeldt는 정확한 알고리즘대한 분류 학적 소개에 대해 설명합니다 ( 슬라이드 | 강의 노트 ).

답변

아직 열 기회는 없었지만 Fomin과 Kratsch의 “정확한 지수 알고리즘”에 관심이있을 것 같습니다 (작년부터).

여기에 목차가 있습니다.

http://www.springerlink.com/content/978-3-642-16532-0#section=800200&page=11&locus=2

나단


답변