Yazar "Sharifov, Firdovsi" seçeneğine göre listele

Listeleniyor 1 - 3 / 3
  • Küçük Resim Yok
    Öğe
    LINEAR PROGRAMMING PROBLEMS WITH FUNDAMENTAL CUT MATRICES
    (Yildiz Technical Univ, 2018) Sharifov, Firdovsi; Kutucu, Hakan
    In the paper, we consider a linear programming problem with con-straint matrices whose rows are 0, 1 characteristics vectors of fundamental cuts in a given undirected graph G = (V, E). We prove that the simplex algorithm finds an optimal solution in at most m-n+1 (m = vertical bar E vertical bar, n = vertical bar V vertical bar) iterations. We also consider the question whether a given binary matrix is a 0, 1 characteristic vector of fundamental cuts in the graph G.
  • Küçük Resim Yok
    Öğe
    Maximum cut problem: new models
    (Ramazan Yaman, 2020) Kutucu, Hakan; Sharifov, Firdovsi
    The maximum cut problem is known to be NP-hard, and consists in determining a partition of the vertices of a given graph such that the sum of the weights of the edges having one end node in each set is maximum. In this paper, we formulate the maximum cut problem as a maximization of a simple non-smooth convex function over the convex hull of bases of the polymatroid associated with a submodular function defined on the subsets of vertices of a given graph. In this way, we show that a greedy-like algorithm with O(mn(2)) time complexity finds a base of a polymatroid that is a solution to the maximum cut problem with different approximation ratio. Moreover, with respect to a base of a polymatroid, we formulate the maximum cut problem as a maximum flow problem between a source and a sink. We then investigate the necessary and sufficient conditions on the optimality of the base in terms of network flow.
  • Küçük Resim Yok
    Öğe
    A NETWORK DESIGN PROBLEM WITH TWO-EDGE MATCHING FAILURES
    (Edp Sciences S A, 2015) Sharifov, Firdovsi; Kutucu, Hakan
    In this paper, we introduce a network design problem with two-edge matching failures. Given a graph, any two edges non-incident to the same node form a two-edge matching. The problem consists in finding a minimum-cost subgraph such that, when deleting any two-edge matching of the graph, every pair of terminal nodes remains connected. We give mixed integer linear programming formulations for the problem and propose a heuristic algorithm based on the Branch-and-Bound method to solve it. We also present computational results.