Browsing by Author "Singireddy, V.R."

Filter results by typing the first few letters
Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    Approximability of Edge-Vertex Domination in Unit Disk Graphs
    (Springer Science and Business Media Deutschland GmbH, 2025) Singireddy, V.R.; Basappa, M.
    Given an undirected graph G=(V,E), a vertex v∈V is edge-vertex (ev) dominated by an edge e∈E if v is either incident to e or incident to an adjacent edge of e. A set Sev⊆E is an edge-vertex dominating set (referred to as ev-dominating set and in short as EVDS) of G if every vertex of G is ev-dominated by at least one edge of Sev. The minimum cardinality of an ev-dominating set is the ev-domination number. The edge-vertex dominating set problem is to find a minimum ev-domination number. The EVDS problem finds applications in handling security issues in the communication network by identifying a minimum number of critical edges to implement additional security measures to safeguard key components of the network. In this paper, we prove that this problem admits a polynomial-time approximation scheme in unit disk graphs. We also give a simple 5-factor linear-time approximation algorithm. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.
  • No Thumbnail Available
    Item
    Integer Linear Programming Models for Variations of the Discrete Semi-obnoxious Facility Location Problem
    (Springer Science and Business Media Deutschland GmbH, 2025) Tushar, C.T.; Singireddy, V.R.; Basappa, M.
    In this work, we consider semi-obnoxious facility location problems, motivated by the following scenario: Suppose an international restaurant brand wants to open a chain of branches in a city that is already occupied by several competing brands. We model this as a geometric optimization problem to provide decision-makers with relevant information on how to economically place k new branches among competitors and how to set prices of items in comparison to nearby competitors. We refer to this as the discrete k-semi-obnoxious facility location (DSofl) problem, classifying it within the context of similar problems in the literature. We introduce two variations of the DSofl problem and propose integer linear programming (ilp) based exact methods for solving both. Additionally, we discuss the implementation of these models using the Gurobi solver. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.