---
_id: '59806'
abstract:
- lang: eng
  text: 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:
- first_name: Ligang
  full_name: Jin, Ligang
  last_name: Jin
- first_name: Eckhard
  full_name: Steffen, Eckhard
  id: '15548'
  last_name: Steffen
  orcid: 0000-0002-9808-7401
citation:
  ama: Jin L, Steffen E. Information dissemination and confusion in signed networks.
    <i>Discrete Applied Mathematics</i>. 2025;373:99-106. doi:<a href="https://doi.org/10.1016/j.dam.2025.04.049">10.1016/j.dam.2025.04.049</a>
  apa: Jin, L., &#38; Steffen, E. (2025). Information dissemination and confusion
    in signed networks. <i>Discrete Applied Mathematics</i>, <i>373</i>, 99–106. <a
    href="https://doi.org/10.1016/j.dam.2025.04.049">https://doi.org/10.1016/j.dam.2025.04.049</a>
  bibtex: '@article{Jin_Steffen_2025, title={Information dissemination and confusion
    in signed networks}, volume={373}, DOI={<a href="https://doi.org/10.1016/j.dam.2025.04.049">10.1016/j.dam.2025.04.049</a>},
    journal={Discrete Applied Mathematics}, publisher={Elsevier BV}, author={Jin,
    Ligang and Steffen, Eckhard}, year={2025}, pages={99–106} }'
  chicago: 'Jin, Ligang, and Eckhard Steffen. “Information Dissemination and Confusion
    in Signed Networks.” <i>Discrete Applied Mathematics</i> 373 (2025): 99–106. <a
    href="https://doi.org/10.1016/j.dam.2025.04.049">https://doi.org/10.1016/j.dam.2025.04.049</a>.'
  ieee: 'L. Jin and E. Steffen, “Information dissemination and confusion in signed
    networks,” <i>Discrete Applied Mathematics</i>, vol. 373, pp. 99–106, 2025, doi:
    <a href="https://doi.org/10.1016/j.dam.2025.04.049">10.1016/j.dam.2025.04.049</a>.'
  mla: Jin, Ligang, and Eckhard Steffen. “Information Dissemination and Confusion
    in Signed Networks.” <i>Discrete Applied Mathematics</i>, vol. 373, Elsevier BV,
    2025, pp. 99–106, doi:<a href="https://doi.org/10.1016/j.dam.2025.04.049">10.1016/j.dam.2025.04.049</a>.
  short: L. Jin, E. Steffen, Discrete Applied Mathematics 373 (2025) 99–106.
date_created: 2025-05-06T07:38:49Z
date_updated: 2025-05-06T07:39:58Z
department:
- _id: '542'
doi: 10.1016/j.dam.2025.04.049
intvolume: '       373'
language:
- iso: eng
page: 99-106
publication: Discrete Applied Mathematics
publication_identifier:
  issn:
  - 0166-218X
publication_status: published
publisher: Elsevier BV
status: public
title: Information dissemination and confusion in signed networks
type: journal_article
user_id: '15540'
volume: 373
year: '2025'
...
---
_id: '51351'
author:
- first_name: Eckhard
  full_name: Steffen, Eckhard
  id: '15548'
  last_name: Steffen
  orcid: 0000-0002-9808-7401
- first_name: Isaak Hieronymus
  full_name: Wolf, Isaak Hieronymus
  id: '88145'
  last_name: Wolf
citation:
  ama: Steffen E, Wolf IH. Bounds for the chromatic index of signed multigraphs. <i>Discrete
    Applied Mathematics</i>. 2023;337:185-189. doi:<a href="https://doi.org/10.1016/j.dam.2023.05.008">10.1016/j.dam.2023.05.008</a>
  apa: Steffen, E., &#38; Wolf, I. H. (2023). Bounds for the chromatic index of signed
    multigraphs. <i>Discrete Applied Mathematics</i>, <i>337</i>, 185–189. <a href="https://doi.org/10.1016/j.dam.2023.05.008">https://doi.org/10.1016/j.dam.2023.05.008</a>
  bibtex: '@article{Steffen_Wolf_2023, title={Bounds for the chromatic index of signed
    multigraphs}, volume={337}, DOI={<a href="https://doi.org/10.1016/j.dam.2023.05.008">10.1016/j.dam.2023.05.008</a>},
    journal={Discrete Applied Mathematics}, publisher={Elsevier BV}, author={Steffen,
    Eckhard and Wolf, Isaak Hieronymus}, year={2023}, pages={185–189} }'
  chicago: 'Steffen, Eckhard, and Isaak Hieronymus Wolf. “Bounds for the Chromatic
    Index of Signed Multigraphs.” <i>Discrete Applied Mathematics</i> 337 (2023):
    185–89. <a href="https://doi.org/10.1016/j.dam.2023.05.008">https://doi.org/10.1016/j.dam.2023.05.008</a>.'
  ieee: 'E. Steffen and I. H. Wolf, “Bounds for the chromatic index of signed multigraphs,”
    <i>Discrete Applied Mathematics</i>, vol. 337, pp. 185–189, 2023, doi: <a href="https://doi.org/10.1016/j.dam.2023.05.008">10.1016/j.dam.2023.05.008</a>.'
  mla: Steffen, Eckhard, and Isaak Hieronymus Wolf. “Bounds for the Chromatic Index
    of Signed Multigraphs.” <i>Discrete Applied Mathematics</i>, vol. 337, Elsevier
    BV, 2023, pp. 185–89, doi:<a href="https://doi.org/10.1016/j.dam.2023.05.008">10.1016/j.dam.2023.05.008</a>.
  short: E. Steffen, I.H. Wolf, Discrete Applied Mathematics 337 (2023) 185–189.
date_created: 2024-02-14T17:33:29Z
date_updated: 2024-02-14T17:33:59Z
department:
- _id: '542'
doi: 10.1016/j.dam.2023.05.008
intvolume: '       337'
keyword:
- Applied Mathematics
- Discrete Mathematics and Combinatorics
language:
- iso: eng
page: 185-189
publication: Discrete Applied Mathematics
publication_identifier:
  issn:
  - 0166-218X
publication_status: published
publisher: Elsevier BV
status: public
title: Bounds for the chromatic index of signed multigraphs
type: journal_article
user_id: '15540'
volume: 337
year: '2023'
...
---
_id: '33950'
author:
- first_name: Chiara
  full_name: Cappello, Chiara
  id: '72874'
  last_name: Cappello
- first_name: Eckhard
  full_name: Steffen, Eckhard
  id: '15548'
  last_name: Steffen
  orcid: 0000-0002-9808-7401
citation:
  ama: Cappello C, Steffen E. Frustration-critical signed graphs. <i>Discrete Applied
    Mathematics</i>. 2022;322:183-193. doi:<a href="https://doi.org/10.1016/j.dam.2022.08.010">10.1016/j.dam.2022.08.010</a>
  apa: Cappello, C., &#38; Steffen, E. (2022). Frustration-critical signed graphs.
    <i>Discrete Applied Mathematics</i>, <i>322</i>, 183–193. <a href="https://doi.org/10.1016/j.dam.2022.08.010">https://doi.org/10.1016/j.dam.2022.08.010</a>
  bibtex: '@article{Cappello_Steffen_2022, title={Frustration-critical signed graphs},
    volume={322}, DOI={<a href="https://doi.org/10.1016/j.dam.2022.08.010">10.1016/j.dam.2022.08.010</a>},
    journal={Discrete Applied Mathematics}, publisher={Elsevier BV}, author={Cappello,
    Chiara and Steffen, Eckhard}, year={2022}, pages={183–193} }'
  chicago: 'Cappello, Chiara, and Eckhard Steffen. “Frustration-Critical Signed Graphs.”
    <i>Discrete Applied Mathematics</i> 322 (2022): 183–93. <a href="https://doi.org/10.1016/j.dam.2022.08.010">https://doi.org/10.1016/j.dam.2022.08.010</a>.'
  ieee: 'C. Cappello and E. Steffen, “Frustration-critical signed graphs,” <i>Discrete
    Applied Mathematics</i>, vol. 322, pp. 183–193, 2022, doi: <a href="https://doi.org/10.1016/j.dam.2022.08.010">10.1016/j.dam.2022.08.010</a>.'
  mla: Cappello, Chiara, and Eckhard Steffen. “Frustration-Critical Signed Graphs.”
    <i>Discrete Applied Mathematics</i>, vol. 322, Elsevier BV, 2022, pp. 183–93,
    doi:<a href="https://doi.org/10.1016/j.dam.2022.08.010">10.1016/j.dam.2022.08.010</a>.
  short: C. Cappello, E. Steffen, Discrete Applied Mathematics 322 (2022) 183–193.
date_created: 2022-10-28T06:51:31Z
date_updated: 2023-05-16T10:36:51Z
department:
- _id: '542'
doi: 10.1016/j.dam.2022.08.010
external_id:
  arxiv:
  - '2112.02664'
intvolume: '       322'
keyword:
- Applied Mathematics
- Discrete Mathematics and Combinatorics
language:
- iso: eng
page: 183-193
publication: Discrete Applied Mathematics
publication_identifier:
  issn:
  - 0166-218X
publication_status: published
publisher: Elsevier BV
status: public
title: Frustration-critical signed graphs
type: journal_article
user_id: '15540'
volume: 322
year: '2022'
...
---
_id: '17658'
abstract:
- lang: eng
  text: '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:
- first_name: Reuven
  full_name: Bar-Yehuda, Reuven
  last_name: Bar-Yehuda
- first_name: Gleb
  full_name: Polevoy, Gleb
  id: '83983'
  last_name: Polevoy
- first_name: Dror
  full_name: Rawitz, Dror
  last_name: Rawitz
citation:
  ama: Bar-Yehuda R, Polevoy G, Rawitz D. Bandwidth allocation in cellular networks
    with multiple interferences. <i>Discrete Applied Mathematics </i>. 2015;194:23-36.
    doi:<a href="http://dx.doi.org/10.1016/j.dam.2015.05.013">http://dx.doi.org/10.1016/j.dam.2015.05.013</a>
  apa: Bar-Yehuda, R., Polevoy, G., &#38; Rawitz, D. (2015). Bandwidth allocation
    in cellular networks with multiple interferences. <i>Discrete Applied Mathematics
    </i>, <i>194</i>, 23–36. <a href="http://dx.doi.org/10.1016/j.dam.2015.05.013">http://dx.doi.org/10.1016/j.dam.2015.05.013</a>
  bibtex: '@article{Bar-Yehuda_Polevoy_Rawitz_2015, title={Bandwidth allocation in
    cellular networks with multiple interferences}, volume={194}, DOI={<a href="http://dx.doi.org/10.1016/j.dam.2015.05.013">http://dx.doi.org/10.1016/j.dam.2015.05.013</a>},
    journal={Discrete Applied Mathematics }, publisher={Elsevier}, author={Bar-Yehuda,
    Reuven and Polevoy, Gleb and Rawitz, Dror}, year={2015}, pages={23–36} }'
  chicago: 'Bar-Yehuda, Reuven, Gleb Polevoy, and Dror Rawitz. “Bandwidth Allocation
    in Cellular Networks with Multiple Interferences.” <i>Discrete Applied Mathematics
    </i> 194 (2015): 23–36. <a href="http://dx.doi.org/10.1016/j.dam.2015.05.013">http://dx.doi.org/10.1016/j.dam.2015.05.013</a>.'
  ieee: R. Bar-Yehuda, G. Polevoy, and D. Rawitz, “Bandwidth allocation in cellular
    networks with multiple interferences,” <i>Discrete Applied Mathematics </i>, vol.
    194, pp. 23–36, 2015.
  mla: Bar-Yehuda, Reuven, et al. “Bandwidth Allocation in Cellular Networks with
    Multiple Interferences.” <i>Discrete Applied Mathematics </i>, vol. 194, Elsevier,
    2015, pp. 23–36, doi:<a href="http://dx.doi.org/10.1016/j.dam.2015.05.013">http://dx.doi.org/10.1016/j.dam.2015.05.013</a>.
  short: R. Bar-Yehuda, G. Polevoy, D. Rawitz, Discrete Applied Mathematics  194 (2015)
    23–36.
date_created: 2020-08-06T15:21:15Z
date_updated: 2022-01-06T06:53:16Z
department:
- _id: '63'
- _id: '541'
doi: http://dx.doi.org/10.1016/j.dam.2015.05.013
extern: '1'
intvolume: '       194'
keyword:
- Local ratio
language:
- iso: eng
page: 23 - 36
publication: 'Discrete Applied Mathematics '
publication_identifier:
  issn:
  - 0166-218X
publisher: Elsevier
status: public
title: Bandwidth allocation in cellular networks with multiple interferences
type: journal_article
user_id: '83983'
volume: 194
year: '2015'
...
---
_id: '23881'
abstract:
- lang: eng
  text: 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:
- first_name: Ulrich
  full_name: Faigle, Ulrich
  last_name: Faigle
- first_name: Gereon
  full_name: Frahling, Gereon
  last_name: Frahling
citation:
  ama: Faigle U, Frahling G. A combinatorial algorithm for weighted stable sets in
    bipartite graphs. <i>Discrete Applied Mathematics</i>. 2006:1380-1391. doi:<a
    href="https://doi.org/10.1016/j.dam.2005.05.037">10.1016/j.dam.2005.05.037</a>
  apa: Faigle, U., &#38; Frahling, G. (2006). A combinatorial algorithm for weighted
    stable sets in bipartite graphs. <i>Discrete Applied Mathematics</i>, 1380–1391.
    <a href="https://doi.org/10.1016/j.dam.2005.05.037">https://doi.org/10.1016/j.dam.2005.05.037</a>
  bibtex: '@article{Faigle_Frahling_2006, title={A combinatorial algorithm for weighted
    stable sets in bipartite graphs}, DOI={<a href="https://doi.org/10.1016/j.dam.2005.05.037">10.1016/j.dam.2005.05.037</a>},
    journal={Discrete Applied Mathematics}, author={Faigle, Ulrich and Frahling, Gereon},
    year={2006}, pages={1380–1391} }'
  chicago: Faigle, Ulrich, and Gereon Frahling. “A Combinatorial Algorithm for Weighted
    Stable Sets in Bipartite Graphs.” <i>Discrete Applied Mathematics</i>, 2006, 1380–91.
    <a href="https://doi.org/10.1016/j.dam.2005.05.037">https://doi.org/10.1016/j.dam.2005.05.037</a>.
  ieee: U. Faigle and G. Frahling, “A combinatorial algorithm for weighted stable
    sets in bipartite graphs,” <i>Discrete Applied Mathematics</i>, pp. 1380–1391,
    2006.
  mla: Faigle, Ulrich, and Gereon Frahling. “A Combinatorial Algorithm for Weighted
    Stable Sets in Bipartite Graphs.” <i>Discrete Applied Mathematics</i>, 2006, pp.
    1380–91, doi:<a href="https://doi.org/10.1016/j.dam.2005.05.037">10.1016/j.dam.2005.05.037</a>.
  short: U. Faigle, G. Frahling, Discrete Applied Mathematics (2006) 1380–1391.
date_created: 2021-09-07T12:54:05Z
date_updated: 2022-01-06T06:56:02Z
department:
- _id: '63'
doi: 10.1016/j.dam.2005.05.037
language:
- iso: eng
page: 1380-1391
publication: Discrete Applied Mathematics
publication_identifier:
  issn:
  - 0166-218X
publication_status: published
status: public
title: A combinatorial algorithm for weighted stable sets in bipartite graphs
type: journal_article
user_id: '15415'
year: '2006'
...
---
_id: '19815'
author:
- first_name: Hans
  full_name: Kleine Büning, Hans
  last_name: Kleine Büning
- first_name: Theodor
  full_name: Lettmann, Theodor
  id: '315'
  last_name: Lettmann
  orcid: 0000-0001-5859-2457
citation:
  ama: Kleine Büning H, Lettmann T. Resolution remains hard under equivalence. <i>Discrete
    Applied Mathematics</i>. 1999:139-148. doi:<a href="https://doi.org/10.1016/s0166-218x(99)00055-4">10.1016/s0166-218x(99)00055-4</a>
  apa: Kleine Büning, H., &#38; Lettmann, T. (1999). Resolution remains hard under
    equivalence. <i>Discrete Applied Mathematics</i>, 139–148. <a href="https://doi.org/10.1016/s0166-218x(99)00055-4">https://doi.org/10.1016/s0166-218x(99)00055-4</a>
  bibtex: '@article{Kleine Büning_Lettmann_1999, title={Resolution remains hard under
    equivalence}, DOI={<a href="https://doi.org/10.1016/s0166-218x(99)00055-4">10.1016/s0166-218x(99)00055-4</a>},
    journal={Discrete Applied Mathematics}, author={Kleine Büning, Hans and Lettmann,
    Theodor}, year={1999}, pages={139–148} }'
  chicago: Kleine Büning, Hans, and Theodor Lettmann. “Resolution Remains Hard under
    Equivalence.” <i>Discrete Applied Mathematics</i>, 1999, 139–48. <a href="https://doi.org/10.1016/s0166-218x(99)00055-4">https://doi.org/10.1016/s0166-218x(99)00055-4</a>.
  ieee: H. Kleine Büning and T. Lettmann, “Resolution remains hard under equivalence,”
    <i>Discrete Applied Mathematics</i>, pp. 139–148, 1999.
  mla: Kleine Büning, Hans, and Theodor Lettmann. “Resolution Remains Hard under Equivalence.”
    <i>Discrete Applied Mathematics</i>, 1999, pp. 139–48, doi:<a href="https://doi.org/10.1016/s0166-218x(99)00055-4">10.1016/s0166-218x(99)00055-4</a>.
  short: H. Kleine Büning, T. Lettmann, Discrete Applied Mathematics (1999) 139–148.
date_created: 2020-10-01T08:13:12Z
date_updated: 2022-01-06T06:54:13Z
department:
- _id: '34'
- _id: '355'
- _id: '7'
doi: 10.1016/s0166-218x(99)00055-4
language:
- iso: eng
page: 139-148
publication: Discrete Applied Mathematics
publication_identifier:
  issn:
  - 0166-218X
publication_status: published
status: public
title: Resolution remains hard under equivalence
type: journal_article
user_id: '315'
year: '1999'
...