2022

Bazgan, Cristina; Casel, Katrin; Cazals, Pierre Dense Graph Partitioning on sparse and dense graphs.Scandinavian Workshop Algorithm Theory (SWAT) 2022
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We consider the problem of partitioning a graph into a non-fixed number of non-overlapping subgraphs of maximum density. The density of a partition is the sum of the densities of the subgraphs, where the density of a subgraph is its average degree, that is, the ratio of its number of edges and its number of vertices. This problem, called Dense Graph Partition, is known to be NP-hard on general graphs and polynomial-time solvable on trees, and polynomial-time 2-approximable. In this paper we study the restriction of Dense Graph Partition to particular sparse and dense graph classes. In particular, we prove that it is NP-hard on dense bipartite graphs as well as on cubic graphs. On dense graphs on \(n\) vertices, it is polynomial-time solvable on graphs with minimum degree \(n-3\) and NP-hard on \((n-4)\)-regular graphs. We prove that it is polynomial-time 4/3-approximable on cubic graphs and admits an efficient polynomial-time approximation scheme on graphs of minimum degree \(n-t\) for any constant \(t\geq 4\).
@inproceedings{bazgan2022dense, abstract = {We consider the problem of partitioning a graph into a non-fixed number of non-overlapping subgraphs of maximum density. The density of a partition is the sum of the densities of the subgraphs, where the density of a subgraph is its average degree, that is, the ratio of its number of edges and its number of vertices. This problem, called Dense Graph Partition, is known to be NP-hard on general graphs and polynomial-time solvable on trees, and polynomial-time 2-approximable. In this paper we study the restriction of Dense Graph Partition to particular sparse and dense graph classes. In particular, we prove that it is NP-hard on dense bipartite graphs as well as on cubic graphs. On dense graphs on \(n\) vertices, it is polynomial-time solvable on graphs with minimum degree \(n-3\) and NP-hard on \((n-4)\)-regular graphs. We prove that it is polynomial-time 4/3-approximable on cubic graphs and admits an efficient polynomial-time approximation scheme on graphs of minimum degree \(n-t\) for any constant \(t\geq 4\).}, author = {Bazgan, Cristina and Casel, Katrin and Cazals, Pierre}, booktitle = {Scandinavian Workshop Algorithm Theory (SWAT)}, keywords = {katrincasel swat year2022}, title = {Dense Graph Partitioning on sparse and dense graphs.}, year = 2022 }

2012

Doerr, Benjamin; Fouz, Mahmoud; Friedrich, Tobias Asynchronous Rumor Spreading in Preferential Attachment GraphsScandinavian Symposium and Workshops on Algorithm Theory (SWAT) 2012: 307–315
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We show that the asynchronous push-pull protocol spreads rumors in preferential attachment graphs (as defined by Barabasi and Albert) in time \(O(\sqrt{\log n})\) to all but a lower order fraction of the nodes with high probability. This is significantly faster than what synchronized protocols can achieve; an obvious lower bound for these is the average distance, which is known to be \(\Theta(\log n / \log\log n)\).
@inproceedings{DBLP:conf/swat/DoerrFF12, abstract = {We show that the asynchronous push-pull protocol spreads rumors in preferential attachment graphs (as defined by Barabasi and Albert) in time \(O(\sqrt{\log n})\) to all but a lower order fraction of the nodes with high probability. This is significantly faster than what synchronized protocols can achieve; an obvious lower bound for these is the average distance, which is known to be \(\Theta(\log n / \log\log n)\).}, author = {Doerr, Benjamin and Fouz, Mahmoud and Friedrich, Tobias}, booktitle = {Scandinavian Symposium and Workshops on Algorithm Theory (SWAT)}, keywords = {imported swat tobiasfriedrich year2012}, pages = {307-315}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Asynchronous Rumor Spreading in Preferential Attachment Graphs}, volume = 7357, year = 2012 }

2006

Ajwani, Deepak; Friedrich, Tobias; Meyer, Ulrich An \(O(n^{2.75})\) Algorithm for Online Topological OrderingScandinavian Workshop on Algorithm Theory (SWAT) 2006: 53–64
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We present a simple algorithm which maintains the topological order of a directed acyclic graph with n nodes under an online edge insertion sequence in \(O(n^{2.75})\) time, independent of the number of edges m inserted. For dense DAGs, this is an improvement over the previous best result of \(O(\min(m^{3/2 \log n, m^3/2 + n^2 \log n)\) by Katriel and Bodlaender. We also provide an empirical comparison of our algorithm with other algorithms for online topological sorting.
@inproceedings{DBLP:conf/swat/AjwaniFM06, abstract = {We present a simple algorithm which maintains the topological order of a directed acyclic graph with n nodes under an online edge insertion sequence in \(O(n^{2.75})\) time, independent of the number of edges m inserted. For dense DAGs, this is an improvement over the previous best result of \(O(\min(m^{3/2} \log n, m^{3/2} + n^2 \log n)\) by Katriel and Bodlaender. We also provide an empirical comparison of our algorithm with other algorithms for online topological sorting.}, author = {Ajwani, Deepak and Friedrich, Tobias and Meyer, Ulrich}, booktitle = {Scandinavian Workshop on Algorithm Theory (SWAT)}, keywords = {noabstract swat tobiasfriedrich year2006}, pages = {53-64}, title = {An \(O(n^{2.75})\) Algorithm for Online Topological Ordering}, year = 2006 }

Doerr, Benjamin; Friedrich, Tobias; Klein, Christian; Osbild, Ralf Unbiased Matrix RoundingScandinavian Symposium and Workshops on Algorithm Theory (SWAT) 2006: 102–112
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We show several ways to round a real matrix to an integer one such that the rounding errors in all rows and columns as well as the whole matrix are less than one. This is a classical problem with applications in many fields, in particular, statistics. We improve earlier solutions of different authors in two ways. For rounding matrices of size \(m \times n\), we reduce the runtime from \(O((mn)^2)\) to \(O(mn \log(mn))\). Second, our roundings also have a rounding error of less than one in all initial intervals of rows and columns. Consequently, arbitrary intervals have an error of at most two. This is particularly useful in the statistics application of controlled rounding. The same result can be obtained via (dependent) randomized rounding. This has the additional advantage that the rounding is unbiased, that is, for all entries \(y_{ij}\) of our rounding, we have \(E(y_{ij}) = x_{ij}\), where \(x_{ij}\) is the corresponding entry of the input matrix.
@inproceedings{DBLP:conf/swat/DoerrFKO06, abstract = {We show several ways to round a real matrix to an integer one such that the rounding errors in all rows and columns as well as the whole matrix are less than one. This is a classical problem with applications in many fields, in particular, statistics. We improve earlier solutions of different authors in two ways. For rounding matrices of size \(m \times n\), we reduce the runtime from \(O((mn)^2)\) to \(O(mn \log(mn))\). Second, our roundings also have a rounding error of less than one in all initial intervals of rows and columns. Consequently, arbitrary intervals have an error of at most two. This is particularly useful in the statistics application of controlled rounding. The same result can be obtained via (dependent) randomized rounding. This has the additional advantage that the rounding is unbiased, that is, for all entries \(y_{ij}\) of our rounding, we have \(E(y_{ij}) = x_{ij}\), where \(x_{ij}\) is the corresponding entry of the input matrix.}, author = {Doerr, Benjamin and Friedrich, Tobias and Klein, Christian and Osbild, Ralf}, booktitle = {Scandinavian Symposium and Workshops on Algorithm Theory (SWAT)}, keywords = {imported swat tobiasfriedrich year2006}, pages = {102-112}, series = {Lecture Notes in Computer Science}, title = {Unbiased Matrix Rounding}, volume = 4059, year = 2006 }