지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 2022.1
- 수록면
- 128 - 133 (6page)
이용수
초록· 키워드
오류제보하기
본 논문은 거리 공간(metric space) 속에 포함된 그래프에서 각 간선의 가중치가 거리 공간 상의 두 끝 정점간의 거리로 주어지는 그래프를 다룬다. 특별히 우리는 이러한 그래프 중 n개 정점을 가진 경로 P에 관해서 연구한다. 우리는 경로 P에 하나의 간선을 추가해서 새로운 그래프 P 얻을 수 있다. 그러면 그래프 P의 두 정점 사이의 최단 경로의 길이를 생각하고 이 길이들 중 최댓값에 주목한다. 이 최댓값을 그래프 P의 지름(diameter)라고 부른다. 우리는 그래프 P의 지름이 최소가 되도록 추가하는 간선을 찾고 싶다. 특별히 임의의 실수 λ> 0에 대해서, P의 지름이 λ이하가 되는 추가 간선이 존재하는지 여부를 결정하는 문제에 대해 O(n) 시간 알고리즘을 제안한다. 이것은 이전 알려진 시간복잡도 O(nlogn)개선한다. 이 결정 알고리즘을 이용해서 주어진 경로 P의 길이 D에 대해서, P의 지름의 최솟값을 찾는 O(nlogD)시간 알고리즘을 제안한다.
목차
요약
ABSTRACT
Ⅰ. 서론
Ⅱ. 관련 연구
Ⅲ. 정의
Ⅳ. 알고리즘
Ⅴ. 결론
REFERENCES
참고문헌 (14)
참고문헌 신청
U. Grobe, C. Knauer, F. Stehn, J. Gudmundsson, and M. Smid, “Fast algorithms for diameter-optimally augmenting paths and trees,” International Journal of Foundations of Computer Science, vol. 30, pp. 293-313, Jan. 2019.
N. Megiddo, “Applying parallel computation algorithms in the design of serial algorithms,” Journal of the ACM, vol. 30, pp. 852-865, Jan. 1983.
D. Bilo, “Almost optimal algorithms for diameter-optimally augmenting trees,” in Proceedings of the 29th International Symposium on Algorithms and Computation, pp. 40:1-40:13, 2018.
E. Oh and H. K. Ahn, “A near-optimal algorithm for finding an optimal shortcut of a tree,” in Proceedings of the 27th International Symposium on Algorithms and Computation, pp. 59:1-59:12, 2016.
N. Alon, A. Gyarfas, and M. Ruszinko, “Decreasing the diameter of bounded degree graphs,” Journal of Graph Theory, vol. 35, pp. 161-172, Sep. 2000.
N. Megiddo, “Applying parallel computation algorithms in the design of serial algorithms,” Journal of the ACM, vol. 30, pp. 852-865, Jan. 1983.
D. Bilo, “Almost optimal algorithms for diameter-optimally augmenting trees,” in Proceedings of the 29th International Symposium on Algorithms and Computation, pp. 40:1-40:13, 2018.
E. Oh and H. K. Ahn, “A near-optimal algorithm for finding an optimal shortcut of a tree,” in Proceedings of the 27th International Symposium on Algorithms and Computation, pp. 59:1-59:12, 2016.
N. Alon, A. Gyarfas, and M. Ruszinko, “Decreasing the diameter of bounded degree graphs,” Journal of Graph Theory, vol. 35, pp. 161-172, Sep. 2000.
함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
Efficient Shortest Path Techniques on a Summarized Graph based on the Relationships
Journal of KIISE
2017 .07
-
이질형 그래프에서의 간선 예측을 위한 고차 그래프 뉴럴 네트워크
한국정보과학회 학술발표논문집
2021 .06
-
GPU를 이용한 경로 기반 하이브리드 그래프 처리 기법
정보과학회 컴퓨팅의 실제 논문지
2024 .11
-
고차 그래프 뉴럴 네트워크를 활용한 이질형 그래프에서의 링크 예측
정보과학회 컴퓨팅의 실제 논문지
2022 .08
-
GPU에서 CUDA를 이용한 그래프 유사도 측정을 위한 병렬 알고리즘
정보과학회 컴퓨팅의 실제 논문지
2017 .03
-
그래프 국소 정보 추출을 통한 분할 알고리즘 기반 그래프 분류 방법
한국정보과학회 학술발표논문집
2021 .12
-
전달성 커널을 사용한 그래프 컨볼루션 네트워크 기반 간선 예측
한국정보과학회 학술발표논문집
2021 .06
-
요약 그래프 상에서 효과적인 그래프 압축 기법
한국정보과학회 학술발표논문집
2016 .06
-
가중 그래프의 편집 거리 예측 모델
한국정보과학회 학술발표논문집
2021 .12
-
부분 그래프 동형 문제를 위한 동적 매칭 순서들의 성능 비교
정보과학회 컴퓨팅의 실제 논문지
2020 .01
-
동형 서브그래프 질의 처리를 위한 효율적인 그래프 경로 기반 인덱싱 기법
정보과학회 컴퓨팅의 실제 논문지
2018 .05
-
An Embedding Technique for Weighted Graphs using LSTM Autoencoders
Journal of KIISE
2021 .01
-
Hyperbolic Graph Transformer Networks for non-Euclidean Data Analysis on Heterogeneous Graphs
Journal of KIISE
2021 .02
-
효과적인 도로 상황 인지를 위한 도로 객체 그래프 모델링 방법
JOURNAL OF PLATFORM TECHNOLOGY
2021 .12
-
동적 그래프에서 효율적인 그래프 요약 기법
한국정보과학회 학술발표논문집
2015 .12
-
그래프의 정점 연결성에 대한 최소 범위 할당
한국정보통신학회논문지
2017 .11
-
외부 지식 그래프 결합을 위한 그래프 트랜스포머 알고리즘
한국정보과학회 학술발표논문집
2023 .06
-
확장 그래프에서 그래프 신경망을 사용한 다 기준 추천
한국통신학회 학술대회논문집
2023 .02
-
Missing Value Imputation Based on Graph Neural Networks Using Auxiliary Feature
정보과학회 컴퓨팅의 실제 논문지
2023 .07
-
분산 환경에서 서브 그래프 탐색을 위한 경로 질의 기반 그래프 처리 기법
한국정보과학회 학술발표논문집
2018 .06
이 논문의 저자 정보
이 논문과 함께 이용한 논문
최근 본 자료
댓글(0)
0