그래프 :: 삭제 수축의 복잡성?

"n"정점과 "m"가장자리의 그래프 G에 고전적인 삭제 축소 알고리즘을 적용하고 있습니다. O (1.6180^(N + m))그래프 :: 삭제 수축의 복잡성?

Z (G) = Z (G-E) + Z (G/E) 위키에서는

, http://en.wikipedia.org/wiki/Chromatic_polynomial#Deletion.E2.80.93contraction

그들은 복잡도 인 것을 말한다. Mi의 주요 질문은 왜 그들이 복잡성에있는 정점의 수를 포함 했느냐입니다. 재귀가 가장자리의 수에만 의존한다는 것이 명백 할 때.

삭제 수축 가장 가까운 참조

는 계산 복잡성 허버트 S. 윌프의 알고리즘에서 설명되는 피보나치 시퀀스와 복잡성 책 http://www.math.upenn.edu/~wilf/AlgComp3.html 18-19 페이지입니다.

모든 도움을 환영합니다.

출처

2012-01-11 labotsirc

the pdf version 페이지 46을보십시오. 삭제 및 수축은 각각 엣지 수를 1 씩 줄이므로 모서리의 재발은 Z (G)가 O (2 ^m) 인 것으로 나타 났지만 O (Fib (n + m))보다 sparsest 그래프. 에지뿐만 아니라 꼭지점을 고려할 때 개선 된 점은 자체 루프가 형성 될 때 즉시 다항식이 0이라는 것을 알 수 있습니다.

출처

2012-01-11 02:22:05 scowl

Scowl, 다른 페이지의 표시에 감사드립니다. 분 (O (2^m), O (fib^(n + m)))은 내가 찾고있는 것이어야합니다. 왜냐하면 나는 또한 자체 루프와 단일 브리지에 최적화를 적용하기 때문에 다른 것들도 (n 직렬 및 n 병렬 에지). 불명확 한 점은 2^m 비용에 대한 삼각형 예제 나 내가 만든 asumptions에 대한 오류를 지적한 상수 인 경우입니다. – labotsirc

그래프 :: 삭제 수축의 복잡성?

답변

관련 문제