Filtreler

2007 - 200912020 - 20221
Filtreleri Sıfırla

Ayarlar

Konu: Graph theory × WoS Q: Q4 ×

Arama Sonuçları

Listeleniyor 1 - 2 / 2
  • Küçük Resim
    Yayın
    On the maximum cardinality cut problem in proper interval graphs and related graph classes
    (Elsevier B.V., 2022-01-04) Boyacı, Arman; Ekim, Tınaz; Shalom, Mordechai
    Although it has been claimed in two different papers that the maximum cardinality cut problem is polynomial-time solvable for proper interval graphs, both of them turned out to be erroneous. In this work we consider the parameterized complexity of this problem. We show that the maximum cardinality cut problem in proper/unit interval graphs is FPT when parameterized by the maximum number of non-empty bubbles in a column of its bubble model. We then generalize this result to a more general graph class by defining new parameters related to the well-known clique-width parameter. Specifically, we define an (?,?,?)-clique-width decomposition of a graph as a clique-width decomposition in which at each step the following invariant is preserved: after discarding at most ? labels, a) every label consists of at most ? sets of twin vertices, and b) all the labels together induce a graph with independence number at most ?. We show that for every two constants ?,?>0 the problem is FPT when parameterized by ? plus the smallest width of an (?,?,?)-clique-width decomposition.
  • Küçük Resim
    Yayın
    Crossing minimization in weighted bipartite graphs
    (Springer, 2007) Çakıroğlu, Olca Arda; Erten, Cesim; Karataş, Ömer; Sözdinler, Melih
    Given a bipartite graph G = (L-0, L-1, E) and a fixed ordering of the nodes in L-0, the problem of finding an ordering of the nodes in L-1 that minimizes the number of crossings has received much attention in literature. The problem is NP-complete in general and several practically efficient heuristics and polynomial-time algorithms with a constant approximation ratio have been suggested. We generalize the problem and consider the version where the edges have nonnegative weights. Although this problem is more general and finds specific applications in automatic graph layout problems similar to those of the unweighted case, it has not received as much attention. We provide a new technique that efficiently approximates a solution to this more general problem within a constant approximation ratio of 3. In addition we provide appropriate generalizations of some common heuristics usually employed for the unweighted case and compare their performances.