@article{59806,
  abstract     = {{We introduce a model of information dissemination in signed networks. It is a discrete-time process in which uninformed actors incrementally receive information from their informed neighbors or from the outside. Our goal is to minimize the number of confused actors — that is, the number of actors who receive contradictory information. We prove upper bounds for the number of confused actors in signed networks and in equivalence classes of signed networks. In particular, we show that there are signed networks where, for any information placement strategy, almost 60% of the actors are confused. Furthermore, this is also the case when considering the minimum number of confused actors within an equivalence class of signed graphs.}},
  author       = {{Jin, Ligang and Steffen, Eckhard}},
  issn         = {{0166-218X}},
  journal      = {{Discrete Applied Mathematics}},
  pages        = {{99--106}},
  publisher    = {{Elsevier BV}},
  title        = {{{Information dissemination and confusion in signed networks}}},
  doi          = {{10.1016/j.dam.2025.04.049}},
  volume       = {{373}},
  year         = {{2025}},
}

@article{51351,
  author       = {{Steffen, Eckhard and Wolf, Isaak Hieronymus}},
  issn         = {{0166-218X}},
  journal      = {{Discrete Applied Mathematics}},
  keywords     = {{Applied Mathematics, Discrete Mathematics and Combinatorics}},
  pages        = {{185--189}},
  publisher    = {{Elsevier BV}},
  title        = {{{Bounds for the chromatic index of signed multigraphs}}},
  doi          = {{10.1016/j.dam.2023.05.008}},
  volume       = {{337}},
  year         = {{2023}},
}

@article{33950,
  author       = {{Cappello, Chiara and Steffen, Eckhard}},
  issn         = {{0166-218X}},
  journal      = {{Discrete Applied Mathematics}},
  keywords     = {{Applied Mathematics, Discrete Mathematics and Combinatorics}},
  pages        = {{183--193}},
  publisher    = {{Elsevier BV}},
  title        = {{{Frustration-critical signed graphs}}},
  doi          = {{10.1016/j.dam.2022.08.010}},
  volume       = {{322}},
  year         = {{2022}},
}

@article{17658,
  abstract     = {{Abstract We study the problem of bandwidth allocation with multiple interferences. In this problem the input consists of a set of users and a set of base stations. Each user has a list of requests, each consisting of a base station, a frequency demand, and a profit that may be gained by scheduling this request. The goal is to find a maximum profit set of user requests S that satisfies the following conditions: (i) S contains at most one request per user, (ii) the frequency sets allotted to requests in S that correspond to the same base station are pairwise non-intersecting, and (iii) the QoS received by any user at any frequency is reasonable according to an interference model. In this paper we consider two variants of bandwidth allocation with multiple interferences. In the first each request specifies a demand that can be satisfied by any subset of frequencies that is large enough. In the second each request specifies a specific frequency interval. Furthermore, we consider two interference models, multiplicative and additive. We show that these problems are extremely hard to approximate if the interferences depend on both the interfered and the interfering base stations. On the other hand, we provide constant factor approximation algorithms for both variants of bandwidth allocation with multiple interferences for the case where the interferences depend only on the interfering base stations. We also consider a restrictive special case that is closely related to the Knapsack problem. We show that this special case is NP-hard and that it admits an FPTAS. }},
  author       = {{Bar-Yehuda, Reuven and Polevoy, Gleb and Rawitz, Dror}},
  issn         = {{0166-218X}},
  journal      = {{Discrete Applied Mathematics }},
  keywords     = {{Local ratio}},
  pages        = {{23 -- 36}},
  publisher    = {{Elsevier}},
  title        = {{{Bandwidth allocation in cellular networks with multiple interferences}}},
  doi          = {{http://dx.doi.org/10.1016/j.dam.2015.05.013}},
  volume       = {{194}},
  year         = {{2015}},
}

@article{23881,
  abstract     = {{Computing a maximum weighted stable set in a bipartite graph is considered well-solved and usually approached with preflow-push, Ford–Fulkerson or network simplex algorithms. We present a combinatorial algorithm for the problem that is not based on flows. Numerical tests suggest that this algorithm performs quite well in practice and is competitive with flow based algorithms especially in the case of dense graphs.}},
  author       = {{Faigle, Ulrich and Frahling, Gereon}},
  issn         = {{0166-218X}},
  journal      = {{Discrete Applied Mathematics}},
  pages        = {{1380--1391}},
  title        = {{{A combinatorial algorithm for weighted stable sets in bipartite graphs}}},
  doi          = {{10.1016/j.dam.2005.05.037}},
  year         = {{2006}},
}

@article{19815,
  author       = {{Kleine Büning, Hans and Lettmann, Theodor}},
  issn         = {{0166-218X}},
  journal      = {{Discrete Applied Mathematics}},
  pages        = {{139--148}},
  title        = {{{Resolution remains hard under equivalence}}},
  doi          = {{10.1016/s0166-218x(99)00055-4}},
  year         = {{1999}},
}