0
가장자리의 절반 이상을 그래프로 잘라내는 욕심 많은 알고리즘을 찾는 사람이 있습니까?그래프를 자르거나 가장자리의 절반 이상을 자르십시오.
올바른 방법은 DFS를 사용하여 정점을 분리하는 것과 관련이 있다고 생각하지만 확실하지 않습니다.
A
답변
0
Mitzenmacher/Upfal (2005)의 정리 6.3, 129 페이지는 기대치의 절반을 잘라내는 알고리즘을 제공합니다. 위의 코멘트에서 언급 된 위키 피 디아 (Wikipedia) 기사처럼 나는 이것이 덜 우화 될 수 있다고 생각한다.
입력 및 출력 그래프에 대한 가정은 무엇입니까? – mrVoid
그래프가 방향이 바뀌지 않음 –
http://www4.ncsu.edu/~kksivara/ma796s/projects/sahar_report.pdf에 따르면 문제는 'NP'-hard이므로 대부분 해결할만한 적절한 그리 디 알고리즘이 없습니다. – Codor