본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

Valid Inequalities and Facets for the Steiner Problem in a Directed Graph

Myung, Young-Soo  
  • 초록

    In this paper, we describe the facial structure of the steiner problem in a directed graph by formulating it as set covering problem. We first characterize trivial facets and derive a necessary condition for nontrival facets. We also introduce a class of valid inequalities with 0-1 coefficients and show when such inequalities define facets.


  • 주제어

    steiner problem in a directed graph .   valid inequalities facets.  

  • 참고문헌 (14)

    1. On the set covering polytope: Ⅰ. all the facets with coefficients in {0,1,2} , E.Balas;S.M.NG , Mathematical Programming / v.43,pp.57-69,
    2. The steiner tree problem Ⅱ: properties and classes of facets , S.Chopra;M.R.Rao , Mathematical Programming / v.64,pp.231-246,
    3. A catalog of steiner tree formulations , M.X.Goemans;Y.s.Myung , Networks / v.23,pp.19-28,
    4. On the facial structure of the set covering polytope , A.Sassano , Mathematical Programming / v.44,pp.181-202,
    5. Steiner problem in graphs , N.Maculan , Annals of Discrete Mathematics / v.31,pp.185-212,
    6. Packing rooted directed cuts in a weighted directed graph , D.R.Fulkerson , Mathematical Programming / v.6,pp.1-13,
    7. On the uncapacitated plant location problem Ⅰ: Facets and Lifting theorems , D.C.Cho;M.W.Padberg;M.R.Rao , Mathematics of Operations Research / v.8,pp.590-612,
    8. On the 0.1 facets of the set covering polytope , G.Cornuejols;A.Sassano , Mathematical Programming / v.43,pp.45-55,
    9. Steiner problem in networks: a survey , P.Winter , Networks / v.17,pp.129-167,
    10. The steiner tree problemⅠ: formulations, compositions and extension fo facets , S.Chopra;M.R.Rao , Mathematical Programming / v.64,pp.209-230,
    11. Facets of the location polytope , G.Cornuejols;J.M.Thizy , Mathematical Programming / v.23,pp.50-74,
    12. A dual ascent approach to steiner tree problems on a directed graph , R.T.Wong , Mathematical Programming / v.28,pp.271-287,
    13. An integer linear programming approach to the steiner probelm in graphs , Y.P.Aneja , Networks / v.10,pp.167-178,
    14. On the uncapacitated plant location problem Ⅰ: Valid inequalities and facets , D.C. Cho;E.L.Jonson;M.W.Padberg;M.R.Rao , Mathematics of Operations Research / v.8,pp.579-589,

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
  • 한국경영과학회 : 저널
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기