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

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

Enumerating All Spanning Shortest Path Forests with Distance and Capacity Constraints 거리 및 용량 제약이 있는 모든 스패닝 최단 경로 포리스트 열거

Yu NAKAHATA, Jun KAWAHARA, Takashi HORIYAMA, Shoji KASAHARA

  • 조회수

    0

  • 이것을 인용

요약 :

본 논문에서는 그래프로 표시된 대상 지역을 여러 지역으로 분할하여 각 지역이 정확히 하나의 대피소를 포함하도록 하는 대피 계획 문제라고 불리는 그래프 분할 문제의 변형을 연구합니다. 피난로의 교차점을 줄이기 위해 각 지역은 볼록해야 하며, 재난 발생 시 주민이 신속하게 대피할 수 있도록 각 지점에서 대피소까지의 거리를 제한해야 하며, 각 대피소에 배정된 주민의 수가 대피소 수용 인원을 초과하지 않도록 해야 합니다. . 본 논문에서는 연결된 구성 요소의 볼록성을 다음과 같이 공식화합니다. 최단 경로 숲을 관통하는 일반 그래프에 대해 이 다목적 최적화 문제를 해결하기 위한 새로운 알고리즘을 제안합니다. 알고리즘은 단일 분할을 구하는 것뿐만 아니라 기존 알고리즘으로는 처리하기 어려운 위의 복잡한 제약 조건을 만족하는 모든 분할을 동시에 열거합니다. 제로 억제 이진 결정 다이어그램 (ZDD)를 압축된 표현으로 사용합니다. 제안된 알고리즘의 효율성은 실제 지도 데이터를 이용한 실험을 통해 확인되었다. 실험 결과, 제안한 알고리즘은 수백 개의 간선을 갖는 입력 그래프의 모든 제약 조건을 만족하는 수억 개의 파티션을 몇 분 안에 얻을 수 있음을 보여주었다.

발행
IEICE TRANSACTIONS on Fundamentals Vol.E101-A No.9 pp.1363-1374
발행일
2018/09/01
공개일
온라인 ISSN
1745-1337
DOI
10.1587/transfun.E101.A.1363
원고의 종류
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
범주

작성자

Yu NAKAHATA
  Nara Institute of Science and Technology
Jun KAWAHARA
  Nara Institute of Science and Technology
Takashi HORIYAMA
  Saitama University
Shoji KASAHARA
  Nara Institute of Science and Technology

키워드