[논문]Shortest paths in almost acyclic graphs

doi:10.1016/S0167-6377(00)00054-7

지식인프라
지식인프라

연구 활동에 필요한 과학기술정보·데이터, 슈퍼컴퓨팅 자원, 정보분석 도구 등을 제공합니다.
- 지식인프라 전체보기
  
  지식인프라 전체보기
  
  연구 활동에 필요한 과학기술 지식인프라를
  데이터 유형, 연구단계, 이용목적별로 제공합니다.
- 이용목적별 지식인프라
  
  이용목적별 지식인프라
  
  이용자의 소속 유형과 활용 목적에 적합한
  과학기술 지식인프라를 제공합니다.
- 활용 시나리오
  
  활용 시나리오
  
  인프라 기능들 사이에 목적별 워크플로우를 구성하여 과학기술 지식인프라 이용에 도움을 드리려고 합니다.
지능형 분석
지능형 분석

과학기술정보데이터, 슈퍼컴퓨팅활용, 정보분석 등
연구자들이 언제 어디서나 활용할 수 있도록 지원합니다.
- AI 논문 서비스・AI-Helper
  
  AI 논문 서비스・AI-Helper
  
  논문의 문장분류를 기반으로 AI 요약 서비스를
  제공하고 있으며, 딥러닝 AI 모델을 통해 연구주제,
  연구방법, 연구결과에 대한 문장분류 태그를
  자동으로 구축하고 있습니다.
  
  또한, 논문 PDF에서 선택한 텍스트를 요약, 번역,
  용어 설명하는 AI-Helper 서비스를 제공합니다.
- ScienceON TREND
  
  ScienceON TREND
  
  최신 과학기술 트렌드와 토픽에 대한 ScienceON
  연관 콘텐츠 및 내외부 지식인프라 콘텐츠를 한 번에 볼 수 있는 서비스입니다.
- ScienceON Analytics
  
  ScienceON Analytics
  
  ScienceON 이용통계 기반의 활용도 분석 서비스를 제공합니다.
- ScienceON LAB
  
  ScienceON LAB
  
  ScienceON LAB은 사용자들이 ScienceON의
  새로운 서비스, 기능 등을 이용해보고 피드백을
  남길 수 있는 공간입니다.
고객지원
고객지원

이용자의 연구 활동을 돕고 요구사항을 반영하고자
온오프라인을 통해 적극적으로 고객을 지원합니다.
- 공지사항
  
  공지사항
  
  ScienceON, 연구개발, 과학기술 활동과 관련된
  공지 내용을 제공합니다.
- FAQ
  
  FAQ
  
  ScienceON 이용과 관련한 주요 질문과 답변을
  제공합니다.
- Q&A
  
  Q&A
  
  ScienceON 이용 관련 질문, 불편사항,
  개선 요청사항에 대한 게시판입니다.
- 사용설명서
  
  사용설명서
  
  ScienceON 사용에 필요한 설명을 제공합니다.
- OpenAPI
  
  ScienceON API Gateway
  
  KISTI에서 구축한 과학기술정보를 제공하는
  개방형 유통 플랫폼입니다.
- ScienceON 홍보
  
  ScienceON 홍보
  
  ScienceON에서 발간한 ScienceON 홍보자료를 확인할 수 있습니다.
- 저작권 관리 안내
  
  저작권 관리 안내
  
  ScienceON에서 제공하는 콘텐츠에 대한 저작권 관리 안내입니다
About
About

ScienceON 개요, 추진방향, 목표, 기능과
제공 콘텐츠입니다.
- ScienceON 개요
  
  ScienceON 개요
  
  과학기술 지식인프라 ScienceON은 과학기술정보, 연구데이터, 정보분석서비스 및 연구인프라를 연계·융합하여 연구자가 필요로 하는 지식인프라를 한곳에서 제공하는 서비스 입니다.
- 추진방향
  
  추진방향
  
  지식인프라의 통합적 연계·활용 중심에서 인공지능
  큐레이션 서비스로의 진화를 목표로 합니다.
- 서비스 목표
  
  서비스 목표
  
  이용자의 접근성과 활용성 강화, R&D의 효율성 향상, 과학기술의 대중화 실현하고자 합니다.
- 주요기능
  
  주요기능
  
  지식인프라, 지능형 분석, 고객지원 등 연구 활동에
  필요한 주요 기능을 설명합니다.
- 제공콘텐츠
  
  제공콘텐츠
  
  ScienceON에서 제공하는 과학기술정보 및
  지식인프라에 대한 개요 및 현황을 제공합니다.
- 지식인프라 소개
  
  지식인프라 소개
  
  ScienceON에서 제공하는 다양한
  지식인프라에 대한 소개를 제공합니다.

인기검색어
급상승검색어

연합인증

연합인증 가입 기관의 연구자들은 소속기관의 인증정보(ID와 암호)를 이용해 다른 대학, 연구기관, 서비스 공급자의 다양한 온라인 자원과 연구 데이터를 이용할 수 있습니다.

이는 여행자가 자국에서 발행 받은 여권으로 세계 각국을 자유롭게 여행할 수 있는 것과 같습니다.

연합인증으로 이용이 가능한 서비스는 NTIS, DataON, Edison, Kafe, Webinar 등이 있습니다.

한번의 인증절차만으로 연합인증 가입 서비스에 추가 로그인 없이 이용이 가능합니다.

다만, 연합인증을 위해서는 최초 1회만 인증 절차가 필요합니다. (회원이 아닐 경우 회원 가입이 필요합니다.)

연합인증 절차는 다음과 같습니다.

최초이용시에는
ScienceON에 로그인 → 연합인증 서비스 접속 → 로그인 (본인 확인 또는 회원가입) → 서비스 이용

그 이후에는
ScienceON 로그인 → 연합인증 서비스 접속 → 서비스 이용

연합인증을 활용하시면 KISTI가 제공하는 다양한 서비스를 편리하게 이용하실 수 있습니다.

[해외논문] Shortest paths in almost acyclic graphs

Operations research letters : a journal of the Operations Research Society of America, v.27 no.4, 2000년, pp.143 - 147

Wagner, Donald K. (Mathematical, Computer, and Information Sciences Division, Office of Naval Research, Arlington, VA 22217-5660, USA)

Abstract ▼ AI-Helper

AbstractThis paper presents an algorithm for the shortest-path problem on a directed graph having arbitrary arc weights. One feature of the algorithm is its ability to exploit a certain type of structure. Two examples of this feature are highlighted. The first example is when the given graph is “almost” acyclic in the sense that there exists a small subset T of nodes, the deletion of which yields an acyclic graph. In this case, a version of the algorithm solves the shortest-path problem in O(|T|m) time; this bound is at least as good as the O(mn) time bound of Bellman (Quart. Appl. Math. 16 (1958) 87–90). The second example is when the weight vector is “almost” nonnegative in the sense that only a small subset F of arcs of the given graph have negative weight. In this case, the algorithm runs in O(min{|F|,n}(m+nlogn)) time.

참고문헌 (5)

Ahuja 1993 Network Flows: Theory, Algorithms, and Applications
Quart. Appl. Math. Bellman 16 87 1958 10.1090/qam/102435 On a routing problem

상세보기
Inform. Process. Lett. Eades 47 418 1993 10.1016/0020-0190(93)90079-O A fast and effective heuristic for the feedback arc set problem

상세보기
Garey 1979 Computers and Intractability: A Guide to the Theory of NP-Completeness
J. Combin. Optim. Pardalos 2 399 1999 10.1023/A:1009736921890 A greedy randomized adaptive search procedure for the feedback vertex set problem

상세보기

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

AI-Helper

안녕하세요, AI-Helper입니다. 좌측 "선택된 텍스트"에서 텍스트를 선택하여 요약, 번역, 용어설명을 실행하세요.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.

선택된 텍스트

맨위로

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

[해외논문] Shortest paths in almost acyclic graphs

Abstract ▼ AI-Helper

참고문헌 (5)

이 논문을 인용한 문헌

관련 콘텐츠

원문 URL 링크

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트