최대 최소도를 가진 스패닝 트리 찾기

Question

연결된 무향 그래프가 주어지면, 최소 최대도를 갖는 스패닝 트리를 찾는 문제는 잘 연구 된 바 있습니다 (M. F¨urer, B. Raghvachari, "minimum degree spanning 트리는 최적의 정도에서 하나의 범위 내에서 ", ACM-SIAM Symposium on Discrete Algorithms (SODA), 1992). 문제는 NP 하드이며 근사 알고리즘은 참조로 설명되었습니다.

다음과 같은 문제에 관심이 있습니다 - 연결되지 않은 무 방향성 그래프 G = (V1, V2, E)가 주어지면 모든 내부 노드 (리프가 아닌 노드)에 대해 최대 최소 차수의 스패닝 트리를 찾습니다. 누군가이 문제가 연구되었는지 말해 줄 수 있습니까? NP-hard입니까 아니면 그것을 해결하기위한 다항식 시간 알고리즘이 있습니까? 또한, 그래프는 편의상 2 부분으로 간주 될 수 있습니다. 예브게니 Kluev의 코멘트에서 언급 한 바와 같이

Answer 1

, A (유한) 나무의 잎도 1이 (그렇지, 사이클이 존재하는 것과 구조는 트리 없을 것이다.)

을 당신이를 찾기 위해 의미 대신하는 경우 연결된 무향 그래프 G상의 가능한 모든 스패닝 트리 중에서 최대 차수의 노드를 갖는 스패닝 트리를 생성하고, 그 루트 R이 G의 모든 노드들 중 최대 차수를 갖는 G의 노드 M 인 스패닝 트리를 형성하고, 모든 이웃들 M의 아이들은 R.

Answer 2

정확한 커버가 3 세트로 보이면이 문제를 줄일 수 있습니다. 차수 4의 정점을 기준으로 3 세트를 표현합니다. 각 세트는 3 개의 에지가 있으며 원래의 문제 인스턴스에있는 요소를 나타내는 3 개의 노드로 연결됩니다. 추가적인 네 번째 가장자리는 모든 "3 세트"노드를 단일 꼭지점 V에 연결합니다.

이 그래프는 모든 가장자리가 "3 세트"노드와 "요소"노드 (또는 V) 사이에 있음을 나타냅니다. 이제이 그래프에는 원래 문제에 해가있는 경우에만 최대 최소 차수 = 4의 스패닝 트리가 있습니다.

분명히 노드 V가 트리의 최대 최소 차수를 낮추지 않도록 3 세트가 충분해야하지만,이 제한은 문제의 NP 경도를 변경하지 않습니다.