IDEAS home Printed from https://ideas.repec.org/a/wly/jnljam/v2019y2019i1n9520324.html

On the Location of a Constrained k−Tree Facility in a Tree Network with Unreliable Edges

Author

Listed:
  • Abdallah W. Aboutahoun
  • Eman Fares

Abstract

Given a tree network T with n vertices where each edge has an independent operational probability, we are interested in finding the optimal location of a reliable service provider facility in a shape of subtree with exactly k leaves and with a diameter of at most l which maximizes the expected number of nodes that are reachable from the selected subtree by operational paths. Demand requests for service originate at perfectly reliable nodes. So, the major concern of this paper is to find a location of a reliable tree‐shaped facility on the network in order to provide a maximum access to network services by ensuring the highest level of network connectivity between the demand nodes and the facility. An efficient algorithm for finding a reliable (k, l) – tree core of T is developed. The time complexity of the proposed algorithm is O(lkn). Examples are provided to illustrate the performance of the proposed algorithm.

Suggested Citation

  • Abdallah W. Aboutahoun & Eman Fares, 2019. "On the Location of a Constrained k−Tree Facility in a Tree Network with Unreliable Edges," Journal of Applied Mathematics, John Wiley & Sons, vol. 2019(1).
    • Handle: RePEc:wly:jnljam:v:2019:y:2019:i:1:n:9520324
    DOI: 10.1155/2019/9520324
    as

    Download full text from publisher

    File URL: https://doi.org/10.1155/2019/9520324
    Download Restriction: no
    File URL: https://libkey.io/10.1155/2019/9520324?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Wei Ding & Yu Zhou & Guangting Chen & Hongfa Wang & Guangming Wang, 2013. "On the 2-MRS Problem in a Tree with Unreliable Edges," Journal of Applied Mathematics, Hindawi, vol. 2013, pages 1-11, November.
    2. Mary E. Helander & Emanuel Melachrinoudis, 1997. "Facility Location and Reliable Route Planning in Hazardous Material Transportation," Transportation Science, INFORMS, vol. 31(3), pages 216-226, August.
    3. Wei Ding & Yu Zhou & Guangting Chen & Hongfa Wang & Guangming Wang, 2013. "On the 2‐MRS Problem in a Tree with Unreliable Edges," Journal of Applied Mathematics, John Wiley & Sons, vol. 2013(1).
    4. G. Y. Handler, 1973. "Minimax Location of a Facility in an Undirected Tree Graph," Transportation Science, INFORMS, vol. 7(3), pages 287-293, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Wei Ding & Ke Qiu, 2018. "A quadratic time exact algorithm for continuous connected 2-facility location problem in trees," Journal of Combinatorial Optimization, Springer, vol. 36(4), pages 1262-1298, November.
    2. Hongfa Wang & Wei Ding, 2014. "Weighted Cache Location Problem with Identical Servers," Journal of Applied Mathematics, John Wiley & Sons, vol. 2014(1).
    3. Zvi Drezner & G. O. Wesolowsky, 1991. "Facility location when demand is time dependent," Naval Research Logistics (NRL), John Wiley & Sons, vol. 38(5), pages 763-777, October.
    4. Wei Ding & Yu Zhou & Guangting Chen & Hongfa Wang & Guangming Wang, 2013. "On the 2‐MRS Problem in a Tree with Unreliable Edges," Journal of Applied Mathematics, John Wiley & Sons, vol. 2013(1).
    5. Noltemeier, H. & Spoerhase, J. & Wirth, H.-C., 2007. "Multiple voting location and single voting location on trees," European Journal of Operational Research, Elsevier, vol. 181(2), pages 654-667, September.
    6. O Berman & Z Drezner, 2003. "A probabilistic one-centre location problem on a network," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(8), pages 871-877, August.
    7. Mulder, H.M. & Pelsmajer, M.J. & Reid, K.B., 2006. "Generalized centrality in trees," Econometric Institute Research Papers EI 2006-16, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    8. Misagh Rahbari & Alireza Arshadi Khamseh & Yaser Sadati-Keneti & Mohammad Javad Jafari, 2022. "A risk-based green location-inventory-routing problem for hazardous materials: NSGA II, MOSA, and multi-objective black widow optimization," Environment, Development and Sustainability: A Multidisciplinary Approach to the Theory and Practice of Sustainable Development, Springer, vol. 24(2), pages 2804-2840, February.
    9. Mehdi Ghiyasvand & Iman Keshtkar, 2024. "Minimizing the expense transmission time from the source node to demand nodes," Journal of Combinatorial Optimization, Springer, vol. 47(3), pages 1-18, April.
    10. Oded Berman & Zvi Drezner & George O. Wesolowsky, 2002. "The collection depots location problem on networks," Naval Research Logistics (NRL), John Wiley & Sons, vol. 49(1), pages 15-24, February.
    11. Becker, Ronald I. & Lari, Isabella & Scozzari, Andrea, 2007. "Algorithms for central-median paths with bounded length on trees," European Journal of Operational Research, Elsevier, vol. 179(3), pages 1208-1220, June.
    12. Wei Ding & Ke Qiu, 2017. "An FPTAS for generalized absolute 1-center problem in vertex-weighted graphs," Journal of Combinatorial Optimization, Springer, vol. 34(4), pages 1084-1095, November.
    13. Esmaeil Afrashteh & Behrooz Alizadeh & Fahimeh Baroughi, 2020. "Optimal approaches for upgrading selective obnoxious p-median location problems on tree networks," Annals of Operations Research, Springer, vol. 289(2), pages 153-172, June.
    14. Yan Sun & Maoxiang Lang & Danzhu Wang, 2016. "Bi-Objective Modelling for Hazardous Materials Road–Rail Multimodal Routing Problem with Railway Schedule-Based Space–Time Constraints," IJERPH, MDPI, vol. 13(8), pages 1-31, July.
    15. Chunsong Bai & Jun Du, 2024. "The Constrained 2-Maxian Problem on Cycles," Mathematics, MDPI, vol. 12(6), pages 1-9, March.
    16. Xinqiang Qian & Xiucui Guan & Junhua Jia & Panos M. Pardalos, 2024. "Inverse Vertex/Absolute Quickest 1-Center Location Problem on a Tree Under Weighted $$l_1$$ l 1 Norm," Journal of Optimization Theory and Applications, Springer, vol. 200(2), pages 524-554, February.
    17. Xinqiang Qian & Xiucui Guan & Junhua Jia & Qiao Zhang & Panos M. Pardalos, 2023. "Vertex quickest 1-center location problem on trees and its inverse problem under weighted $$l_\infty $$ l ∞ norm," Journal of Global Optimization, Springer, vol. 85(2), pages 461-485, February.
    18. Puerto, Justo & Tamir, Arie & Perea, Federico, 2011. "A cooperative location game based on the 1-center location problem," European Journal of Operational Research, Elsevier, vol. 214(2), pages 317-330, October.
    19. Wolfgang Steitz, 2015. "New Heuristic Approaches for the Bounded-Diameter Minimum Spanning Tree Problem," INFORMS Journal on Computing, INFORMS, vol. 27(1), pages 151-163, February.
    20. Van Huy Pham & Nguyen Chi Tam, 2019. "A combinatorial algorithm for the ordered 1-median problem on cactus graphs," OPSEARCH, Springer;Operational Research Society of India, vol. 56(3), pages 780-789, September.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wly:jnljam:v:2019:y:2019:i:1:n:9520324. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Wiley Content Delivery (email available below). General contact details of provider: https://onlinelibrary.wiley.com/journal/4185 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.