6 Search Results for "Schuster, Martin R."


Document
PACE Solver Description
PACE Solver Description: Fluid

Authors: Max Bannach, Sebastian Berndt, Martin Schuster, and Marcel Wienöbst

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)


Abstract
This document describes the heuristic for computing treedepth decompositions of undirected graphs used by our solve fluid. The heuristic runs four different strategies to find a solution and finally outputs the best solution obtained by any of them. Two strategies are score-based and iteratively remove the vertex with the best score. The other two strategies iteratively search for vertex separators and remove them. We also present implementation strategies and data structures that significantly improve the run time complexity and might be interesting on their own.

Cite as

Max Bannach, Sebastian Berndt, Martin Schuster, and Marcel Wienöbst. PACE Solver Description: Fluid. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 27:1-27:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{bannach_et_al:LIPIcs.IPEC.2020.27,
  author =	{Bannach, Max and Berndt, Sebastian and Schuster, Martin and Wien\"{o}bst, Marcel},
  title =	{{PACE Solver Description: Fluid}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{27:1--27:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.27},
  URN =		{urn:nbn:de:0030-drops-133300},
  doi =		{10.4230/LIPIcs.IPEC.2020.27},
  annote =	{Keywords: treedepth, heuristics}
}
Document
PACE Solver Description
PACE Solver Description: PID^⋆

Authors: Max Bannach, Sebastian Berndt, Martin Schuster, and Marcel Wienöbst

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)


Abstract
This document provides a short overview of our treedepth solver PID^{⋆} in the version that we submitted to the exact track of the PACE challenge 2020. The solver relies on the positive-instance driven dynamic programming (PID) paradigm that was discovered in the light of earlier iterations of the PACE in the context of treewidth. It was recently shown that PID can be used to solve a general class of vertex pursuit-evasion games - which include the game theoretic characterization of treedepth. Our solver PID^{⋆} is build on top of this characterization.

Cite as

Max Bannach, Sebastian Berndt, Martin Schuster, and Marcel Wienöbst. PACE Solver Description: PID^⋆. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 28:1-28:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{bannach_et_al:LIPIcs.IPEC.2020.28,
  author =	{Bannach, Max and Berndt, Sebastian and Schuster, Martin and Wien\"{o}bst, Marcel},
  title =	{{PACE Solver Description: PID^⋆}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{28:1--28:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.28},
  URN =		{urn:nbn:de:0030-drops-133312},
  doi =		{10.4230/LIPIcs.IPEC.2020.28},
  annote =	{Keywords: treedepth, positive-instance driven}
}
Document
New Abilities and Limitations of Spectral Graph Bisection

Authors: Martin R. Schuster and Maciej Liskiewicz

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)


Abstract
Spectral based heuristics belong to well-known commonly used methods which determines provably minimal graph bisection or outputs "fail" when the optimality cannot be certified. In this paper we focus on Boppana's algorithm which belongs to one of the most prominent methods of this type. It is well known that the algorithm works well in the random planted bisection model - the standard class of graphs for analysis minimum bisection and relevant problems. In 2001 Feige and Kilian posed the question if Boppana's algorithm works well in the semirandom model by Blum and Spencer. In our paper we answer this question affirmatively. We show also that the algorithm achieves similar performance on graph classes which extend the semirandom model. Since the behavior of Boppana's algorithm on the semirandom graphs remained unknown, Feige and Kilian proposed a new semidefinite programming (SDP) based approach and proved that it works on this model. The relationship between the performance of the SDP based algorithm and Boppana's approach was left as an open problem. In this paper we solve the problem in a complete way by proving that the bisection algorithm of Feige and Kilian provides exactly the same results as Boppana's algorithm. As a consequence we get that Boppana's algorithm achieves the optimal threshold for exact cluster recovery in the stochastic block model. On the other hand we prove some limitations of Boppana's approach: we show that if the density difference on the parameters of the planted bisection model is too small then the algorithm fails with high probability in the model.

Cite as

Martin R. Schuster and Maciej Liskiewicz. New Abilities and Limitations of Spectral Graph Bisection. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 66:1-66:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{schuster_et_al:LIPIcs.ESA.2017.66,
  author =	{Schuster, Martin R. and Liskiewicz, Maciej},
  title =	{{New Abilities and Limitations of Spectral Graph Bisection}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{66:1--66:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.66},
  URN =		{urn:nbn:de:0030-drops-78658},
  doi =		{10.4230/LIPIcs.ESA.2017.66},
  annote =	{Keywords: Minimum Graph Bisection, Spectral Methods, Convex Programming}
}
Document
Transducer-Based Rewriting Games for Active XML

Authors: Martin Schuster

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)


Abstract
Context-free games are two-player rewriting games that are played on nested strings representing XML documents with embedded function symbols. These games were introduced to model rewriting processes for intensional documents in the Active XML framework, where input documents are to be rewritten into a given target schema by calls to external services. This paper studies the setting where dependencies between inputs and outputs of service calls are modelled by transducers, which has not been examined previously. It defines transducer models operating on nested words and studies their properties, as well as the computational complexity of the winning problem for transducer-based context-free games in several scenarios. While the complexity of this problem is quite high in most settings (ranging from NP-complete to undecidable), some tractable restrictions are also identified.

Cite as

Martin Schuster. Transducer-Based Rewriting Games for Active XML. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 83:1-83:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{schuster:LIPIcs.MFCS.2016.83,
  author =	{Schuster, Martin},
  title =	{{Transducer-Based Rewriting Games for Active XML}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{83:1--83:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.83},
  URN =		{urn:nbn:de:0030-drops-64910},
  doi =		{10.4230/LIPIcs.MFCS.2016.83},
  annote =	{Keywords: active XML, computational complexity, nested words, transducers, rewriting games}
}
Document
Games for Active XML Revisited

Authors: Martin Schuster and Thomas Schwentick

Published in: LIPIcs, Volume 31, 18th International Conference on Database Theory (ICDT 2015)


Abstract
The paper studies the rewriting mechanisms for intensional documents in the Active XML framework, abstracted in the form of active context-free games. The safe rewriting problem studied in this paper is to decide whether the first player, Juliet, has a winning strategy for a given game and (nested) word; this corresponds to a successful rewriting strategy for a given intensional document. The paper examines several extensions to active context-free games. The primary extension allows more expressive schemas (namely XML schemas and regular nested word languages) for both target and replacement languages and has the effect that games are played on nested words instead of (flat) words as in previous studies. Other extensions consider validation of input parameters of web services, and an alternative semantics based on insertion of service call results. In general, the complexity of the safe rewriting problem is highly intractable (doubly exponential time), but the paper identifies interesting tractable cases.

Cite as

Martin Schuster and Thomas Schwentick. Games for Active XML Revisited. In 18th International Conference on Database Theory (ICDT 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 31, pp. 60-75, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{schuster_et_al:LIPIcs.ICDT.2015.60,
  author =	{Schuster, Martin and Schwentick, Thomas},
  title =	{{Games for Active XML Revisited}},
  booktitle =	{18th International Conference on Database Theory (ICDT 2015)},
  pages =	{60--75},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-79-8},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{31},
  editor =	{Arenas, Marcelo and Ugarte, Mart{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2015.60},
  URN =		{urn:nbn:de:0030-drops-49773},
  doi =		{10.4230/LIPIcs.ICDT.2015.60},
  annote =	{Keywords: Active XML, Computational Complexity, Nested Words, Rewriting Games, Semistructured Data}
}
Document
Polyglutamine and Polyalanine Tracts Are Enriched in Transcription Factors of Plants

Authors: Nina Kottenhagen, Lydia Gramzow, Fabian Horn, Martin Pohl, and Günter Theißen

Published in: OASIcs, Volume 26, German Conference on Bioinformatics 2012


Abstract
Polyglutamine (polyQ) tracts have been studied extensively for their roles in a number of human diseases such as Huntington's or different Ataxias. However, it has also been recognized that polyQ tracts are abundant and may have important functional and evolutionary roles. Especially the association of polyQ and also polyalanine (polyA) tracts with transcription factors and their activation activity has been noted. While a number of examples for this association have been found for proteins from opisthokonts (animals and fungi), only a few studies exist for polyQ and polyA stretches in plants, and systematic investigations of the significance of these repeats in plant transcription factors are scarce. Here, we analyze the abundance and length of polyQ and polyA stretches in the conceptual proteomes of six plant species and examine the connection between polyQ and polyA tracts and transcription factors of the repeat-containing proteins. We show that there is an association of polyQ stretches with transcription factors in plants. In grasses, transcription factors are also significantly enriched in polyA stretches. While there is variation in the abundance, length, and association with certain functions of polyQ and polyA stretches between different species, no general differences in the evolution of these repeats could be observed between plants and opisthokonts.

Cite as

Nina Kottenhagen, Lydia Gramzow, Fabian Horn, Martin Pohl, and Günter Theißen. Polyglutamine and Polyalanine Tracts Are Enriched in Transcription Factors of Plants. In German Conference on Bioinformatics 2012. Open Access Series in Informatics (OASIcs), Volume 26, pp. 93-107, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@InProceedings{kottenhagen_et_al:OASIcs.GCB.2012.93,
  author =	{Kottenhagen, Nina and Gramzow, Lydia and Horn, Fabian and Pohl, Martin and Thei{\ss}en, G\"{u}nter},
  title =	{{Polyglutamine and Polyalanine Tracts Are Enriched in Transcription Factors of Plants}},
  booktitle =	{German Conference on Bioinformatics 2012},
  pages =	{93--107},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-44-6},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{26},
  editor =	{B\"{o}cker, Sebastian and Hufsky, Franziska and Scheubert, Kerstin and Schleicher, Jana and Schuster, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.GCB.2012.93},
  URN =		{urn:nbn:de:0030-drops-37217},
  doi =		{10.4230/OASIcs.GCB.2012.93},
  annote =	{Keywords: tandem repeats, molecular evolution, GO annotation}
}
  • Refine by Author
  • 4 Schuster, Martin
  • 2 Bannach, Max
  • 2 Berndt, Sebastian
  • 2 Wienöbst, Marcel
  • 1 Gramzow, Lydia
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 2 treedepth
  • 1 Active XML
  • 1 Computational Complexity
  • 1 Convex Programming
  • 1 GO annotation
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2020
  • 1 2012
  • 1 2015
  • 1 2016
  • 1 2017

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