2 Search Results for "Uhlmann, Johannes"

Document
DOI: 10.4230/LIPIcs.SEA.2023.14
A Graph-Theoretic Formulation of Exploratory Blockmodeling

Authors: Alexander Bille, Niels Grüttemeier, Christian Komusiewicz, and Nils Morawietz

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract
We present a new simple graph-theoretic formulation of the exploratory blockmodeling problem on undirected and unweighted one-mode networks. Our formulation takes as input the network G and the maximum number t of blocks for the solution model. The task is to find a minimum-size set of edge insertions and deletions that transform the input graph G into a graph G' with at most t neighborhood classes. Herein, a neighborhood class is a maximal set of vertices with the same neighborhood. The neighborhood classes of G' directly give the blocks and block interactions of the computed blockmodel. We analyze the classic and parameterized complexity of the exploratory blockmodeling problem, provide a branch-and-bound algorithm, an ILP formulation and several heuristics. Finally, we compare our exact algorithms to previous ILP-based approaches and show that the new algorithms are faster for t ≥ 4.
Cite as

Alexander Bille, Niels Grüttemeier, Christian Komusiewicz, and Nils Morawietz. A Graph-Theoretic Formulation of Exploratory Blockmodeling. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 14:1-14:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bille_et_al:LIPIcs.SEA.2023.14,
  author =	{Bille, Alexander and Gr\"{u}ttemeier, Niels and Komusiewicz, Christian and Morawietz, Nils},
  title =	{{A Graph-Theoretic Formulation of Exploratory Blockmodeling}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{14:1--14:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.14},
  URN =		{urn:nbn:de:0030-drops-183648},
  doi =		{10.4230/LIPIcs.SEA.2023.14},
  annote =	{Keywords: Clustering, Exact Algorithms, ILP-Formulation, Branch-and-Bound, Social Networks}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2008.1760
A Cubic-Vertex Kernel for Flip Consensus Tree

Authors: Christian Komusiewicz and Johannes Uhlmann

Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)

Abstract
Given a bipartite graph G=(V_c,V_t,E) and a non-negative integer k, the NP-complete Minimum-Flip Consensus Tree problem asks whether G can be transformed, using up to k edge insertions and deletions, into a graph that does not contain an induced P_5 with its first vertex in V_t (a so-called M-graph or Sigma-graph). This problem plays an important role in computational phylogenetics, V_c standing for the characters and V_t standing for taxa. Chen et al. [IEEE/ACM TCBB 2006] showed that Minimum-Flip Consensus Tree is NP-complete and presented a parameterized algorithm with running time O(6^k\cdot |V_t|\cdot |V_c|). Recently, Boecker et al. [IWPEC'08] presented a refined search tree algorithm with running time O(4.83^k(|V_t|+|V_c|) + |V_t|\cdot |V_c|). We complement these results by polynomial-time executable data reduction rules yielding a problem kernel with O(k^3) vertices.
Cite as

Christian Komusiewicz and Johannes Uhlmann. A Cubic-Vertex Kernel for Flip Consensus Tree. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 280-291, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{komusiewicz_et_al:LIPIcs.FSTTCS.2008.1760,
  author =	{Komusiewicz, Christian and Uhlmann, Johannes},
  title =	{{A Cubic-Vertex Kernel for Flip Consensus Tree}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{280--291},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1760},
  URN =		{urn:nbn:de:0030-drops-17600},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1760},
  annote =	{Keywords: Fixed-parameter algorithm, problem kernel, NP-hard problem, graph modification problem, computational phylogenetics}
}
  • Refine by Author
  • 2 Komusiewicz, Christian
  • 1 Bille, Alexander
  • 1 Grüttemeier, Niels
  • 1 Morawietz, Nils
  • 1 Uhlmann, Johannes

  • Refine by Classification
  • 1 Theory of computation → Branch-and-bound
  • 1 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Theory of computation → Social networks

  • Refine by Keyword
  • 1 Branch-and-Bound
  • 1 Clustering
  • 1 Exact Algorithms
  • 1 Fixed-parameter algorithm
  • 1 ILP-Formulation
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2008
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact