Filtreler

2006 - 200912020 - 20221
Filtreleri Sıfırla

Ayarlar

İndeks: Science Citation Index Expanded (SCI-EXPANDED) × Konu: Graph theory ×

Arama Sonuçları

Listeleniyor 1 - 2 / 2
  • Küçük Resim
    Yayın
    Network synchronization: Spectral versus statistical properties
    (Elsevier B.V., 2006-12) Atay, Fatihcan Mehmet; Bıyıkoğlu, Türker; Jost, Jürgen
    We consider synchronization of weighted networks, possibly with asymmetrical connections. Focusing on causal relations rather than the observed correlations, we show that the synchronizability of networks cannot be directly inferred from their statistical properties. Small local changes in the network structure can sensitively affect the eigenvalues relevant for synchronization, while the gross statistical network properties remain essentially unchanged. Consequently, commonly used statistical properties, including the degree distribution, degree homogeneity, average degree, average distance, degree correlation and clustering coefficient, can fail to characterize the synchronizability of networks in terms of causal relations, despite the observed correlations.
  • 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.