검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

A Scheduling Problem in Multihop Networks 멀티홉 네트워크의 스케줄링 문제

Kaoru WATANABE, Masakazu SENGOKU, Hiroshi TAMURA, Keisuke NAKANO, Shoji SHINODA

  • 조회수

    0

  • 이것을 인용

요약 :

멀티홉 네트워크에서 무선 패킷은 소스에서 대상으로 무선 패킷을 전송하기 위해 중간 스테이션(중계기)을 통해 중계되는 경우가 많습니다. 그래프 이론 모델을 사용하여 다중 홉 네트워크의 스케줄링 문제를 고려합니다. 허락하다 D=(V,A) 정점 세트가 있는 이중 그래프가 됩니다. V 그리고 호 세트 A. 허락하다 f 호에 양의 정수를 표시하십시오. A. 의 가치 f(u,v)는 링크에 할당된 주파수 대역을 의미합니다. uv. 우리는 전화 f 역이행적 if f(u,v)f(v,w) 인접한 호의 경우(u,v)와 (v,w) 의 D. 최소 역이행 라벨링 문제는 역이이 라벨링에 할당된 정수의 개수가 최소가 되도록 최소 역이이 라벨링을 찾는 문제이다. 본 논문에서는 이 문제가 NP-hard임을 증명하고 이에 대한 간단한 분산 근사 알고리즘을 제안합니다.

발행
IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.6 pp.1222-1227
발행일
2000/06/25
공개일
온라인 ISSN
DOI
원고의 종류
PAPER
범주
그래프와 네트워크

작성자

키워드