5 Search Results for "Schmid, Andreas"


Document
A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs

Authors: Parinya Chalermsook, Andreas Schmid, and Sumedha Uniyal

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)


Abstract
A cactus graph is a graph in which any two cycles are edge-disjoint. We present a constructive proof of the fact that any plane graph G contains a cactus subgraph C where C contains at least a 1/6 fraction of the triangular faces of G. We also show that this ratio cannot be improved by showing a tight lower bound. Together with an algorithm for linear matroid parity, our bound implies two approximation algorithms for computing "dense planar structures" inside any graph: (i) A 1/6 approximation algorithm for, given any graph G, finding a planar subgraph with a maximum number of triangular faces; this improves upon the previous 1/11-approximation; (ii) An alternate (and arguably more illustrative) proof of the 4/9 approximation algorithm for finding a planar subgraph with a maximum number of edges. Our bound is obtained by analyzing a natural local search strategy and heavily exploiting the exchange arguments. Therefore, this suggests the power of local search in handling problems of this kind.

Cite as

Parinya Chalermsook, Andreas Schmid, and Sumedha Uniyal. A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{chalermsook_et_al:LIPIcs.STACS.2019.19,
  author =	{Chalermsook, Parinya and Schmid, Andreas and Uniyal, Sumedha},
  title =	{{A Tight Extremal Bound on the Lov\'{a}sz Cactus Number in Planar Graphs}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.19},
  URN =		{urn:nbn:de:0030-drops-102583},
  doi =		{10.4230/LIPIcs.STACS.2019.19},
  annote =	{Keywords: Graph Drawing, Matroid Matching, Maximum Planar Subgraph, Local Search Algorithms}
}
Document
Computing Tutte Paths

Authors: Andreas Schmid and Jens M. Schmidt

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)


Abstract
Tutte paths are one of the most successful tools for attacking problems on long cycles in planar graphs. Unfortunately, results based on them are non-constructive, as their proofs inherently use an induction on overlapping subgraphs and these overlaps prevent any attempt to bound the running time by a polynomial. For special cases however, computational results of Tutte paths are known: For 4-connected planar graphs, Tutte paths are in fact Hamiltonian paths and Chiba and Nishizeki [N. Chiba and T. Nishizeki, 1989] showed how to compute such paths in linear time. For 3-connected planar graphs, Tutte paths have a significantly more complicated structure, and it has only recently been shown that they can be computed in polynomial time [A. Schmid and J. M. Schmidt, 2015]. However, Tutte paths are defined for general 2-connected planar graphs and this is what most applications need. In this unrestricted setting, no computational results for Tutte paths are known. We give the first efficient algorithm that computes a Tutte path (in this unrestricted setting). One of the strongest existence results about such Tutte paths is due to Sanders [D. P. Sanders, 1997], which allows one to prescribe the end vertices and an intermediate edge of the desired path. Encompassing and strengthening all previous computational results on Tutte paths, we show how to compute such a special Tutte path efficiently. Our method refines both, the existence results of Thomassen [C. Thomassen, 1983] and Sanders [D. P. Sanders, 1997], and avoids that the subgraphs arising in the inductive proof intersect in more than one edge by using a novel iterative decomposition along 2-separators. Finally, we show that our algorithm runs in time O(n^2).

Cite as

Andreas Schmid and Jens M. Schmidt. Computing Tutte Paths. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 98:1-98:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{schmid_et_al:LIPIcs.ICALP.2018.98,
  author =	{Schmid, Andreas and Schmidt, Jens M.},
  title =	{{Computing Tutte Paths}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{98:1--98:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.98},
  URN =		{urn:nbn:de:0030-drops-91029},
  doi =		{10.4230/LIPIcs.ICALP.2018.98},
  annote =	{Keywords: Tutte Path, Tutte Cycle, 2-Connected Planar Graph, Hamiltonian Cycle}
}
Document
Computing 2-Walks in Polynomial Time

Authors: Andreas Schmid and Jens M. Schmidt

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)


Abstract
A 2-walk of a graph is a walk visiting every vertex at least once and at most twice. By generalizing decompositions of Tutte and Thomassen, Gao, Richter and Yu proved that every 3-connected planar graph contains a closed 2-walk such that all vertices visited twice are contained in 3-separators. This seminal result generalizes Tutte's theorem that every 4-connected planar graph is Hamiltonian as well as Barnette's theorem that every 3-connected planar graph has a spanning tree with maximum degree at most 3. The algorithmic challenge of finding such a closed 2-walk is to overcome big overlapping subgraphs in the decomposition, which are also inherent in Tutte's and Thomassen's decompositions. We solve this problem by extending the decomposition of Gao, Richter and Yu in such a way that all pieces, in which the graph is decomposed into, are edge-disjoint. This implies the first polynomial-time algorithm that computes the closed 2-walk mentioned above.

Cite as

Andreas Schmid and Jens M. Schmidt. Computing 2-Walks in Polynomial Time. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 676-688, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{schmid_et_al:LIPIcs.STACS.2015.676,
  author =	{Schmid, Andreas and Schmidt, Jens M.},
  title =	{{Computing 2-Walks in Polynomial Time}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{676--688},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.676},
  URN =		{urn:nbn:de:0030-drops-49502},
  doi =		{10.4230/LIPIcs.STACS.2015.676},
  annote =	{Keywords: algorithms and data structures, 2-walks, 3-connected planar graphs, Tutte paths, 3-trees}
}
Document
Customizing Service Platforms (Dagstuhl Seminar 13171)

Authors: Luciano Baresi, Andreas Rummler, and Klaus Schmid

Published in: Dagstuhl Reports, Volume 3, Issue 4 (2013)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13171 "Customizing Service Platforms". The aim of the seminar was to bring together researchers from different areas of academia and industry that are related to the seminar topic and typically do not intensively interact with each other. These communities are Product Line Engineering, Software Architecture, Service Engineering, and Cloud Computing. The ambition of the seminar was to work on the topic of "Customization of Service Platforms", which is related to all of these areas, in a synergistic and cooperative way to identify new research challenges and solution approaches. As part of the seminar, we identified a number of key areas which provided the basis for highly interactive working groups.

Cite as

Luciano Baresi, Andreas Rummler, and Klaus Schmid. Customizing Service Platforms (Dagstuhl Seminar 13171). In Dagstuhl Reports, Volume 3, Issue 4, pp. 114-150, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@Article{baresi_et_al:DagRep.3.4.114,
  author =	{Baresi, Luciano and Rummler, Andreas and Schmid, Klaus},
  title =	{{Customizing Service Platforms (Dagstuhl Seminar 13171)}},
  pages =	{114--150},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{4},
  editor =	{Baresi, Luciano and Rummler, Andreas and Schmid, Klaus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.3.4.114},
  URN =		{urn:nbn:de:0030-drops-41736},
  doi =		{10.4230/DagRep.3.4.114},
  annote =	{Keywords: Service-Oriented Architectures, Service Platforms / Cloud Computing, Product Line Engineering, Variability Management}
}
Document
Error Containment in the Presence of Metastability

Authors: Andreas Steininger

Published in: Dagstuhl Seminar Proceedings, Volume 8371, Fault-Tolerant Distributed Algorithms on VLSI Chips (2009)


Abstract
Error containment is an important concept in fault tolerant system design, and techniques like voting are applied to mask erroneous outputs, thus preventing their propagation. In this presentation we will use the example of DARTS, a fault-tolerant distributed clock generation scheme in hardware, to demonstrate that metastability is a substantial threat to error containment. We will illustrate how metastability can originate and propagate such that a single fault may upset the system. The main conclusion is that modeling efforts on all design levels are definitely required in order to mitigate and quantify the deteriorating effect of metastability on system dependability.

Cite as

Andreas Steininger. Error Containment in the Presence of Metastability. In Fault-Tolerant Distributed Algorithms on VLSI Chips. Dagstuhl Seminar Proceedings, Volume 8371, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{steininger:DagSemProc.08371.3,
  author =	{Steininger, Andreas},
  title =	{{Error Containment in the Presence of Metastability}},
  booktitle =	{Fault-Tolerant Distributed Algorithms on VLSI Chips},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8371},
  editor =	{Bernadette Charron-Bost and Shlomi Dolev and Jo Ebergen and Ulrich Schmid},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08371.3},
  URN =		{urn:nbn:de:0030-drops-19235},
  doi =		{10.4230/DagSemProc.08371.3},
  annote =	{Keywords: Metastability, fault tolerance, clock generation}
}
  • Refine by Author
  • 3 Schmid, Andreas
  • 2 Schmidt, Jens M.
  • 1 Baresi, Luciano
  • 1 Chalermsook, Parinya
  • 1 Rummler, Andreas
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Graph theory

  • Refine by Keyword
  • 1 2-Connected Planar Graph
  • 1 2-walks
  • 1 3-connected planar graphs
  • 1 3-trees
  • 1 Graph Drawing
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 1 2009
  • 1 2013
  • 1 2015
  • 1 2018
  • 1 2019

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