[{"citation":{"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>.","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>","short":"L. Jin, E. Steffen, Discrete Applied Mathematics 373 (2025) 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>.","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>.","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} }","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>"},"status":"public","page":"99-106","_id":"59806","publisher":"Elsevier BV","user_id":"15540","volume":373,"publication":"Discrete Applied Mathematics","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."}],"date_created":"2025-05-06T07:38:49Z","type":"journal_article","department":[{"_id":"542"}],"year":"2025","title":"Information dissemination and confusion in signed networks","author":[{"first_name":"Ligang","last_name":"Jin","full_name":"Jin, Ligang"},{"id":"15548","full_name":"Steffen, Eckhard","first_name":"Eckhard","last_name":"Steffen","orcid":"0000-0002-9808-7401"}],"publication_identifier":{"issn":["0166-218X"]},"date_updated":"2025-05-06T07:39:58Z","publication_status":"published","intvolume":"       373","language":[{"iso":"eng"}],"doi":"10.1016/j.dam.2025.04.049"},{"status":"public","user_id":"15540","volume":337,"page":"185-189","_id":"51351","publisher":"Elsevier BV","citation":{"short":"E. Steffen, I.H. Wolf, Discrete Applied Mathematics 337 (2023) 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>.","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>","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>.","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>","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} }","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>."},"publication_status":"published","date_updated":"2024-02-14T17:33:59Z","intvolume":"       337","year":"2023","title":"Bounds for the chromatic index of signed multigraphs","publication_identifier":{"issn":["0166-218X"]},"author":[{"id":"15548","last_name":"Steffen","first_name":"Eckhard","orcid":"0000-0002-9808-7401","full_name":"Steffen, Eckhard"},{"full_name":"Wolf, Isaak Hieronymus","first_name":"Isaak Hieronymus","last_name":"Wolf","id":"88145"}],"doi":"10.1016/j.dam.2023.05.008","language":[{"iso":"eng"}],"publication":"Discrete Applied Mathematics","type":"journal_article","keyword":["Applied Mathematics","Discrete Mathematics and Combinatorics"],"department":[{"_id":"542"}],"date_created":"2024-02-14T17:33:29Z"},{"status":"public","volume":322,"user_id":"15540","_id":"33950","publisher":"Elsevier BV","page":"183-193","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>","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} }","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.","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>.","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>","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>."},"external_id":{"arxiv":["2112.02664"]},"intvolume":"       322","publication_status":"published","date_updated":"2023-05-16T10:36:51Z","publication_identifier":{"issn":["0166-218X"]},"author":[{"full_name":"Cappello, Chiara","first_name":"Chiara","last_name":"Cappello","id":"72874"},{"id":"15548","orcid":"0000-0002-9808-7401","first_name":"Eckhard","last_name":"Steffen","full_name":"Steffen, Eckhard"}],"title":"Frustration-critical signed graphs","year":"2022","doi":"10.1016/j.dam.2022.08.010","language":[{"iso":"eng"}],"publication":"Discrete Applied Mathematics","department":[{"_id":"542"}],"type":"journal_article","keyword":["Applied Mathematics","Discrete Mathematics and Combinatorics"],"date_created":"2022-10-28T06:51:31Z"},{"page":"23 - 36","_id":"17658","publisher":"Elsevier","user_id":"83983","volume":194,"status":"public","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>","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} }","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>.","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>.","short":"R. Bar-Yehuda, G. Polevoy, D. Rawitz, Discrete Applied Mathematics  194 (2015) 23–36.","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>","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."},"language":[{"iso":"eng"}],"doi":"http://dx.doi.org/10.1016/j.dam.2015.05.013","title":"Bandwidth allocation in cellular networks with multiple interferences","year":"2015","author":[{"full_name":"Bar-Yehuda, Reuven","last_name":"Bar-Yehuda","first_name":"Reuven"},{"id":"83983","first_name":"Gleb","last_name":"Polevoy","full_name":"Polevoy, Gleb"},{"full_name":"Rawitz, Dror","first_name":"Dror","last_name":"Rawitz"}],"publication_identifier":{"issn":["0166-218X"]},"date_updated":"2022-01-06T06:53:16Z","intvolume":"       194","date_created":"2020-08-06T15:21:15Z","keyword":["Local ratio"],"type":"journal_article","department":[{"_id":"63"},{"_id":"541"}],"publication":"Discrete Applied Mathematics ","extern":"1","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":"Ulrich","last_name":"Faigle","full_name":"Faigle, Ulrich"},{"full_name":"Frahling, Gereon","last_name":"Frahling","first_name":"Gereon"}],"publication_identifier":{"issn":["0166-218X"]},"title":"A combinatorial algorithm for weighted stable sets in bipartite graphs","year":"2006","status":"public","date_updated":"2022-01-06T06:56:02Z","publication_status":"published","_id":"23881","language":[{"iso":"eng"}],"page":"1380-1391","doi":"10.1016/j.dam.2005.05.037","user_id":"15415","citation":{"short":"U. Faigle, G. Frahling, Discrete Applied Mathematics (2006) 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>.","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>","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.","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>","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} }","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>."},"publication":"Discrete Applied Mathematics","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."}],"date_created":"2021-09-07T12:54:05Z","department":[{"_id":"63"}],"type":"journal_article"},{"department":[{"_id":"34"},{"_id":"355"},{"_id":"7"}],"type":"journal_article","date_created":"2020-10-01T08:13:12Z","citation":{"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} }","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>","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.","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.","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>"},"publication":"Discrete Applied Mathematics","user_id":"315","doi":"10.1016/s0166-218x(99)00055-4","_id":"19815","language":[{"iso":"eng"}],"page":"139-148","publication_status":"published","date_updated":"2022-01-06T06:54:13Z","publication_identifier":{"issn":["0166-218X"]},"author":[{"last_name":"Kleine Büning","first_name":"Hans","full_name":"Kleine Büning, Hans"},{"full_name":"Lettmann, Theodor","first_name":"Theodor","orcid":"0000-0001-5859-2457","last_name":"Lettmann","id":"315"}],"status":"public","year":"1999","title":"Resolution remains hard under equivalence"}]