25 Search Results for "G�nther, Oliver"

Document
DOI: 10.4230/LIPIcs.IPEC.2022.23
Parameterized Complexity of Maximum Happy Set and Densest k-Subgraph

Authors: Yosuke Mizutani and Blair D. Sullivan

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

Abstract
We present fixed-parameter tractable (FPT) algorithms for two problems, Maximum Happy Set (MaxHS) and Densest k-Subgraph (DkS) - also known as Maximum Edge Happy Set. Given a graph G and an integer k, MaxHS asks for a set S of k vertices such that the number of happy vertices with respect to S is maximized, where a vertex v is happy if v and all its neighbors are in S. We show that MaxHS can be solved in time 𝒪(2^mw ⋅ mw ⋅ k² ⋅ |V(G)|) and 𝒪(8^cw ⋅ k² ⋅ |V(G)|), where mw and cw denote the modular-width and the clique-width of G, respectively. This answers the open questions on fixed-parameter tractability posed in [Asahiro et al., 2021]. The DkS problem asks for a subgraph with k vertices maximizing the number of edges. If we define happy edges as the edges whose endpoints are in S, then DkS can be seen as an edge-variant of MaxHS. In this paper we show that DkS can be solved in time f(nd)⋅|V(G)|^𝒪(1) and 𝒪(2^{cd}⋅ k² ⋅ |V(G)|), where nd and cd denote the neighborhood diversity and the cluster deletion number of G, respectively, and f is some computable function. This result implies that DkS is also fixed-parameter tractable by twin cover number.
Cite as

Yosuke Mizutani and Blair D. Sullivan. Parameterized Complexity of Maximum Happy Set and Densest k-Subgraph. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{mizutani_et_al:LIPIcs.IPEC.2022.23,
  author =	{Mizutani, Yosuke and Sullivan, Blair D.},
  title =	{{Parameterized Complexity of Maximum Happy Set and Densest k-Subgraph}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{23:1--23:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.23},
  URN =		{urn:nbn:de:0030-drops-173795},
  doi =		{10.4230/LIPIcs.IPEC.2022.23},
  annote =	{Keywords: parameterized algorithms, maximum happy set, densest k-subgraph, modular-width, clique-width, neighborhood diversity, cluster deletion number, twin cover}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.5
Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults

Authors: David Adjiashvili, Felix Hommelsheim, Moritz Mühlenthaler, and Oliver Schaudt

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
The Edge-disjoint s-t Paths Problem (s-t EDP) is a classical network design problem whose goal is to connect for some k ≥ 1 two given vertices of a graph under the condition that any k-1 edges of the graph may fail. We extend the simple uniform failure model of the s-t EDP as follows: the edge set of the graph is partitioned into vulnerable, and safe edges, and a set of at most k vulnerable edges may fail, while safe edges do not fail. In particular we study the Fault-Tolerant Path (FTP) problem, the counterpart of the Shortest s-t Path problem in this non-uniform failure model as well as the Fault-Tolerant Flow (FTF) problem, the counterpart of s-t EDP. We present complexity results alongside exact and approximation algorithms for both problems. We emphasize the vast increase in complexity of the problems compared to s-t EDP.
Cite as

David Adjiashvili, Felix Hommelsheim, Moritz Mühlenthaler, and Oliver Schaudt. Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{adjiashvili_et_al:LIPIcs.SWAT.2022.5,
  author =	{Adjiashvili, David and Hommelsheim, Felix and M\"{u}hlenthaler, Moritz and Schaudt, Oliver},
  title =	{{Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{5:1--5:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.5},
  URN =		{urn:nbn:de:0030-drops-161659},
  doi =		{10.4230/LIPIcs.SWAT.2022.5},
  annote =	{Keywords: graph algorithms, network design, fault tolerance, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.36
The Complexity of Approximating the Complex-Valued Potts Model

Authors: Andreas Galanis, Leslie Ann Goldberg, and Andrés Herrera-Poyatos

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
We study the complexity of approximating the partition function of the q-state Potts model and the closely related Tutte polynomial for complex values of the underlying parameters. Apart from the classical connections with quantum computing and phase transitions in statistical physics, recent work in approximate counting has shown that the behaviour in the complex plane, and more precisely the location of zeros, is strongly connected with the complexity of the approximation problem, even for positive real-valued parameters. Previous work in the complex plane by Goldberg and Guo focused on q = 2, which corresponds to the case of the Ising model; for q > 2, the behaviour in the complex plane is not as well understood and most work applies only to the real-valued Tutte plane. Our main result is a complete classification of the complexity of the approximation problems for all non-real values of the parameters, by establishing #P-hardness results that apply even when restricted to planar graphs. Our techniques apply to all q ≥ 2 and further complement/refine previous results both for the Ising model and the Tutte plane, answering in particular a question raised by Bordewich, Freedman, Lovász and Welsh in the context of quantum computations.
Cite as

Andreas Galanis, Leslie Ann Goldberg, and Andrés Herrera-Poyatos. The Complexity of Approximating the Complex-Valued Potts Model. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{galanis_et_al:LIPIcs.MFCS.2020.36,
  author =	{Galanis, Andreas and Goldberg, Leslie Ann and Herrera-Poyatos, Andr\'{e}s},
  title =	{{The Complexity of Approximating the Complex-Valued Potts Model}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{36:1--36:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.36},
  URN =		{urn:nbn:de:0030-drops-127038},
  doi =		{10.4230/LIPIcs.MFCS.2020.36},
  annote =	{Keywords: approximate counting, Potts model, Tutte polynomial, partition function, complex numbers}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.14
Almost Envy-Free Allocations with Connected Bundles

Authors: Vittorio Bilò, Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, and William S. Zwicker

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
We study the existence of allocations of indivisible goods that are envy-free up to one good (EF1), under the additional constraint that each bundle needs to be connected in an underlying item graph G. When the items are arranged in a path, we show that EF1 allocations are guaranteed to exist for arbitrary monotonic utility functions over bundles, provided that either there are at most four agents, or there are any number of agents but they all have identical utility functions. Our existence proofs are based on classical arguments from the divisible cake-cutting setting, and involve discrete analogues of cut-and-choose, of Stromquist's moving-knife protocol, and of the Su-Simmons argument based on Sperner's lemma. Sperner's lemma can also be used to show that on a path, an EF2 allocation exists for any number of agents. Except for the results using Sperner's lemma, all of our procedures can be implemented by efficient algorithms. Our positive results for paths imply the existence of connected EF1 or EF2 allocations whenever G is traceable, i.e., contains a Hamiltonian path. For the case of two agents, we completely characterize the class of graphs G that guarantee the existence of EF1 allocations as the class of graphs whose biconnected components are arranged in a path. This class is strictly larger than the class of traceable graphs; one can check in linear time whether a graph belongs to this class, and if so return an EF1 allocation.
Cite as

Vittorio Bilò, Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, and William S. Zwicker. Almost Envy-Free Allocations with Connected Bundles. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.ITCS.2019.14,
  author =	{Bil\`{o}, Vittorio and Caragiannis, Ioannis and Flammini, Michele and Igarashi, Ayumi and Monaco, Gianpiero and Peters, Dominik and Vinci, Cosimo and Zwicker, William S.},
  title =	{{Almost Envy-Free Allocations with Connected Bundles}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{14:1--14:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.14},
  URN =		{urn:nbn:de:0030-drops-101078},
  doi =		{10.4230/LIPIcs.ITCS.2019.14},
  annote =	{Keywords: Envy-free Division, Cake-cutting, Resource Allocation, Algorithmic Game Theory}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.710
The Minimum Bisection in the Planted Bisection Model

Authors: Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, and Kathrin Skubch

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract
In the planted bisection model a random graph G(n,p_+,p_-) with n vertices is created by partitioning the vertices randomly into two classes of equal size (up to plus or minus 1). Any two vertices that belong to the same class are linked by an edge with probability p_+ and any two that belong to different classes with probability (p_-) <(p_+) independently. The planted bisection model has been used extensively to benchmark graph partitioning algorithms. If (p_+)=2(d_+)/n and (p_-)=2(d_-)/n for numbers 0 <= (d_-) <(d_+) that remain fixed as n tends to infinity, then with high probability the "planted" bisection (the one used to construct the graph) will not be a minimum bisection. In this paper we derive an asymptotic formula for the minimum bisection width under the assumption that (d_+)-(d_-) > c * sqrt((d_+)ln(d_+)) for a certain constant c>0.
Cite as

Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, and Kathrin Skubch. The Minimum Bisection in the Planted Bisection Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 710-725, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{cojaoghlan_et_al:LIPIcs.APPROX-RANDOM.2015.710,
  author =	{Coja-Oghlan, Amin and Cooley, Oliver and Kang, Mihyun and Skubch, Kathrin},
  title =	{{The Minimum Bisection in the Planted Bisection Model}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{710--725},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.710},
  URN =		{urn:nbn:de:0030-drops-53315},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.710},
  annote =	{Keywords: Random graphs, minimum bisection, planted bisection, belief propagation.}
}
Document
DOI: 10.4230/DagSemProc.10131.6
Towards Linguistically-Grounded Spatial Logics

Authors: Joana Hois and Oliver Kutz

Published in: Dagstuhl Seminar Proceedings, Volume 10131, Spatial Representation and Reasoning in Language : Ontologies and Logics of Space (2011)

Abstract
We propose a method to analyze the amount of coverage and adequacy of spatial calculi by relating a calculus to a linguistic ontology for space by using similarities and linguistic corpus data. This allows evaluating whether and where a spatial calculus can be used for natural language interpretation. It can also lead to 'more appropriate' spatial logics for spatial language.
Cite as

Joana Hois and Oliver Kutz. Towards Linguistically-Grounded Spatial Logics. In Spatial Representation and Reasoning in Language : Ontologies and Logics of Space. Dagstuhl Seminar Proceedings, Volume 10131, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{hois_et_al:DagSemProc.10131.6,
  author =	{Hois, Joana and Kutz, Oliver},
  title =	{{Towards Linguistically-Grounded Spatial Logics}},
  booktitle =	{Spatial Representation and Reasoning in Language : Ontologies and Logics of Space},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10131},
  editor =	{John A. Bateman and Anthony G. Cohn and James Pustejovsky},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10131.6},
  URN =		{urn:nbn:de:0030-drops-27296},
  doi =		{10.4230/DagSemProc.10131.6},
  annote =	{Keywords: Spatial Logics, Spatial Language}
}
Document
DOI: 10.4230/DagSemProc.08141.6
Current state of ASoC design methodology

Authors: Andreas Bernauer, Dirk Fritz, Björn Sander, Oliver Bringmann, and Wolfgang Rosenstiel

Published in: Dagstuhl Seminar Proceedings, Volume 8141, Organic Computing - Controlled Self-organization (2008)

Abstract
This paper gives an overview of the current state of ASoC design methodology and presents preliminary results on evaluating the learning classifier system XCS for the control of a QuadCore. The ASoC design methodology can determine system reliability based on activity, power and temperature analysis, together with reliability block diagrams. The evaluation of the XCS shows that in the evaluated setup, XCS can find optimal operating points, even in changed environments or with changed reward functions. This even works, though limited, without the genetic algorithm the XCS uses internally. The results motivate us to continue the evaluation for more complex setups.
Cite as

Andreas Bernauer, Dirk Fritz, Björn Sander, Oliver Bringmann, and Wolfgang Rosenstiel. Current state of ASoC design methodology. In Organic Computing - Controlled Self-organization. Dagstuhl Seminar Proceedings, Volume 8141, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{bernauer_et_al:DagSemProc.08141.6,
  author =	{Bernauer, Andreas and Fritz, Dirk and Sander, Bj\"{o}rn and Bringmann, Oliver and Rosenstiel, Wolfgang},
  title =	{{Current state of ASoC design methodology}},
  booktitle =	{Organic Computing - Controlled Self-organization},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8141},
  editor =	{Kirstie Bellman and Michael G. Hinchey and Christian M\"{u}ller-Schloer and Hartmut Schmeck and Rolf W\"{u}rtz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08141.6},
  URN =		{urn:nbn:de:0030-drops-15646},
  doi =		{10.4230/DagSemProc.08141.6},
  annote =	{Keywords: Dagstuhl Seminar Proceedings, System-on-Chip, design methodology, system reliability, learning classifier system, XCS, ASoC}
}
Document
DOI: 10.4230/DagSemProc.08191.5
08191 Working Group Report – X-graphs of Y-graphs and their Representations

Authors: Vladimir Batagelj, Franz J. Brandenburg, Walter Didimo, Guiseppe Liotta, and Maurizio Patrignani

Published in: Dagstuhl Seminar Proceedings, Volume 8191, Graph Drawing with Applications to Bioinformatics and Social Sciences (2008)

Abstract
We address graph decomposition problems that help the hybrid visualization of large graphs, where different graphic metaphors (node-link, matrix, etc.) are used in the same picture. We generalize the $X$-graphs of $Y$-graphs model introduced by Brandenburg (Brandenburg, F.J.: Graph clustering I: Cycles of cliques. In Di Battista, G., ed.: Graph Drawing (Proc. GD '97). Volume 1353 of Lecture Notes Comput. Sci., Springer-Verlag (1997) 158--168) to formalize the problem of automatically identifying dense subgraphs ($Y$-graphs, clusters) that are prone to be collapsed and shown with a matricial representation when needed. We show that (planar, $K_5$)-recognition, that is, the problem of identifying $K_5$ subgraphs such that the graph obtained by collapsing them is planar, is NP-hard. On the positive side, we show that it is possible to determine the highest value of $k$ such that $G$ is a (planar,$k$-core)-graph in $O(m + n log(n))$ time.
Cite as

Vladimir Batagelj, Franz J. Brandenburg, Walter Didimo, Guiseppe Liotta, and Maurizio Patrignani. 08191 Working Group Report – X-graphs of Y-graphs and their Representations. In Graph Drawing with Applications to Bioinformatics and Social Sciences. Dagstuhl Seminar Proceedings, Volume 8191, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{batagelj_et_al:DagSemProc.08191.5,
  author =	{Batagelj, Vladimir and Brandenburg, Franz J. and Didimo, Walter and Liotta, Guiseppe and Patrignani, Maurizio},
  title =	{{08191 Working Group Report – X-graphs of Y-graphs and their Representations}},
  booktitle =	{Graph Drawing with Applications to Bioinformatics and Social Sciences},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8191},
  editor =	{Stephen P. Borgatti and Stephen Kobourov and Oliver Kohlbacher and Petra Mutzel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08191.5},
  URN =		{urn:nbn:de:0030-drops-15563},
  doi =		{10.4230/DagSemProc.08191.5},
  annote =	{Keywords: Graph drawing, X-graphs of Y-graphs, visualization of large graphs}
}
Document
DOI: 10.4230/DagSemProc.06291.12
Pricing Web Services

Authors: Oliver Günther, Gerrit Tamm, and Frank Leymann

Published in: Dagstuhl Seminar Proceedings, Volume 6291, The Role of Business Processes in Service Oriented Architectures (2006)

Abstract
This paper focuses on the challenges associated with composing and pricing web services. We present the results of an online experiment, where subjects were confronted with a variety of choices and decisions relating to web service markets and service composition. Our analysis shows that people expect the price of a composite web service to be lower than the sum of the prices of the elementary services, i.e., users are not willing to pay for aggregation by a third party. To obtain a viable business model for composed web services, non-standard pricing mechanisms, such as auctions and negotiations, possibly supported by electronic agents, have to be taken into consideration. Usage-based pricing schemes, combined with an option to switch to a flat subscription, seem most appropriate to penetrate the developing web service market.
Cite as

Oliver Günther, Gerrit Tamm, and Frank Leymann. Pricing Web Services. In The Role of Business Processes in Service Oriented Architectures. Dagstuhl Seminar Proceedings, Volume 6291, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{gunther_et_al:DagSemProc.06291.12,
  author =	{G\"{u}nther, Oliver and Tamm, Gerrit and Leymann, Frank},
  title =	{{Pricing Web Services}},
  booktitle =	{The Role of Business Processes in Service Oriented Architectures},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6291},
  editor =	{Frank Leymann and Wolfgang Reisig and Satish R. Thatte and Wil van der Aalst},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06291.12},
  URN =		{urn:nbn:de:0030-drops-8220},
  doi =		{10.4230/DagSemProc.06291.12},
  annote =	{Keywords: Composite web services, pricing}
}
Document
DOI: 10.4230/DagSemProc.05471.3
A machine learning approach for prediction of DNA and peptide HPLC retention times

Authors: Marc Sturm, Sascha Quinten, Christian G. Huber, and Oliver Kohlbacher

Published in: Dagstuhl Seminar Proceedings, Volume 5471, Computational Proteomics (2006)

Abstract
High performance liquid chromatography (HPLC) has become one of the most efficient methods for the separation of biomolecules. It is an important tool in DNA purification after synthesis as well as DNA quantification. In both cases the separability of different oligonucleotides is essential. The prediction of oligonucleotide retention times prior to the experiment may detect superimposed nucleotides and thereby help to avoid futile experiments. In 2002 Gilar et al. proposed a simple mathematical model for the prediction of DNA retention times, that reliably works at high temperatures only (at least 70°C). To cover a wider temperature rang we incorporated DNA secondary structure information in addition to base composition and length. We used support vector regression (SVR) for the model generation and retention time prediction. A similar problem arises in shotgun proteomics. Here HPLC coupled to a mass spectrometer (MS) is used to analyze complex peptide mixtures (thousands of peptides). Predicting peptide retention times can be used to validate tandem-MS peptide identifications made by search engines like SEQUEST. Recently several methods including multiple linear regression and artificial neural networks were proposed, but SVR has not been used so far.
Cite as

Marc Sturm, Sascha Quinten, Christian G. Huber, and Oliver Kohlbacher. A machine learning approach for prediction of DNA and peptide HPLC retention times. In Computational Proteomics. Dagstuhl Seminar Proceedings, Volume 5471, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{sturm_et_al:DagSemProc.05471.3,
  author =	{Sturm, Marc and Quinten, Sascha and Huber, Christian G. and Kohlbacher, Oliver},
  title =	{{A machine learning approach for prediction of DNA and peptide HPLC retention times}},
  booktitle =	{Computational Proteomics},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5471},
  editor =	{Christian G. Huber and Oliver Kohlbacher and Knut Reinert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05471.3},
  URN =		{urn:nbn:de:0030-drops-5484},
  doi =		{10.4230/DagSemProc.05471.3},
  annote =	{Keywords: High performance liquid chromatography, mass spectrometry, retention time, prediction, peptide, DNA, support vector regression}
}
Document
DOI: 10.4230/DagSemProc.05471.13
OpenMS - A Framework for Quantitative HPLC/MS-Based Proteomics

Authors: Knut Reinert, Oliver Kohlbacher, Clemens Gröpl, Eva Lange, Ole Schulz-Trieglaff, Marc Sturm, and Nico Pfeifer

Published in: Dagstuhl Seminar Proceedings, Volume 5471, Computational Proteomics (2006)

Abstract
In the talk we describe the freely available software library OpenMS which is currently under development at the Freie Universität Berlin and the Eberhardt-Karls Universität Tübingen. We give an overview of the goals and problems in differential proteomics with HPLC and then describe in detail the implemented approaches for signal processing, peak detection and data reduction currently employed in OpenMS. After this we describe methods to identify the differential expression of peptides and propose strategies to avoid MS/MS identification of peptides of interest. We give an overview of the capabilities and design principles of OpenMS and demonstrate its ease of use. Finally we describe projects in which OpenMS will be or was already deployed and thereby demonstrate its versatility.
Cite as

Knut Reinert, Oliver Kohlbacher, Clemens Gröpl, Eva Lange, Ole Schulz-Trieglaff, Marc Sturm, and Nico Pfeifer. OpenMS - A Framework for Quantitative HPLC/MS-Based Proteomics. In Computational Proteomics. Dagstuhl Seminar Proceedings, Volume 5471, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{reinert_et_al:DagSemProc.05471.13,
  author =	{Reinert, Knut and Kohlbacher, Oliver and Gr\"{o}pl, Clemens and Lange, Eva and Schulz-Trieglaff, Ole and Sturm, Marc and Pfeifer, Nico},
  title =	{{OpenMS - A Framework for Quantitative HPLC/MS-Based Proteomics}},
  booktitle =	{Computational Proteomics},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5471},
  editor =	{Christian G. Huber and Oliver Kohlbacher and Knut Reinert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05471.13},
  URN =		{urn:nbn:de:0030-drops-5463},
  doi =		{10.4230/DagSemProc.05471.13},
  annote =	{Keywords: Proteomics, C++, Differential expression}
}
Document
DOI: 10.4230/DagSemProc.05471.1
05471 Abstract Collection – Computational Proteomics

Authors: Christian G. Huber, Oliver Kohlbacher, and Knut Reinert

Published in: Dagstuhl Seminar Proceedings, Volume 5471, Computational Proteomics (2006)

Abstract
From 20.11.05 to 25.11.05, the Dagstuhl Seminar 05471 ``Computational Proteomics'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Christian G. Huber, Oliver Kohlbacher, and Knut Reinert. 05471 Abstract Collection – Computational Proteomics. In Computational Proteomics. Dagstuhl Seminar Proceedings, Volume 5471, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{huber_et_al:DagSemProc.05471.1,
  author =	{Huber, Christian G. and Kohlbacher, Oliver and Reinert, Knut},
  title =	{{05471 Abstract Collection – Computational Proteomics}},
  booktitle =	{Computational Proteomics},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5471},
  editor =	{Christian G. Huber and Oliver Kohlbacher and Knut Reinert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05471.1},
  URN =		{urn:nbn:de:0030-drops-5569},
  doi =		{10.4230/DagSemProc.05471.1},
  annote =	{Keywords: Proteomics, mass spectrometry, MALDI, HPLC-MS, differential expression, clinical proteomics, quantitation, identification}
}
Document
DOI: 10.4230/DagSemProc.05471.2
05471 Executive Summary – Computational Proteomics

Authors: Christian G. Huber, Oliver Kohlbacher, and Knut Reinert

Published in: Dagstuhl Seminar Proceedings, Volume 5471, Computational Proteomics (2006)

Abstract
The Dagstuhl Seminar on Computational Proteomics brought together researchers from computer science and from proteomics to discuss the state of the art and future developments at the interface between experiment and theory. This interdisciplinary exchange covered a wide range of topics, from new experimental methods resulting in more complex data we will have to expect in the future to purely theoretical studies of what level of experimental accuracy is required in order to solve certain problems. A particular focus was also on the application side, where the participants discussed more complex experimental methodologies that are enabled by more sophisticated computational techniques. Quantitative aspects of protein expression analysis as well as posttranslational modifications in the context of disease development and diagnosis were discussed. The seminar sparked a number of new ideas and collaborations and resulted in joint grant applications and publications.
Cite as

Christian G. Huber, Oliver Kohlbacher, and Knut Reinert. 05471 Executive Summary – Computational Proteomics. In Computational Proteomics. Dagstuhl Seminar Proceedings, Volume 5471, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{huber_et_al:DagSemProc.05471.2,
  author =	{Huber, Christian G. and Kohlbacher, Oliver and Reinert, Knut},
  title =	{{05471 Executive Summary – Computational Proteomics}},
  booktitle =	{Computational Proteomics},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5471},
  editor =	{Christian G. Huber and Oliver Kohlbacher and Knut Reinert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05471.2},
  URN =		{urn:nbn:de:0030-drops-5406},
  doi =		{10.4230/DagSemProc.05471.2},
  annote =	{Keywords: Proteomics, mass spectrometry, MALDI, HPLC-MS, differential expression, clinical proteomics, quantitation, identification}
}
Document
DOI: 10.4230/DagSemProc.05471.4
An Algorithm for Feature Finding in LC/MS Raw Data

Authors: Clemens Gröpl

Published in: Dagstuhl Seminar Proceedings, Volume 5471, Computational Proteomics (2006)

Abstract
Liquid chromatography coupled with mass spectrometry is an established method in shotgun proteomics. A key step in the data processing pipeline is to transform the raw data acquired by the mass spectrometer into a list of features. In this context, a emph{feature} is defined as the two-dimensional integration with respect to retention time (RT) and mass-over-charge (m/z) of the eluting signal belonging to a single charge variant of a measurand (e.g., a peptide). Features are characterized by attributes like average mass-to-charge ratio, centroid retention time, intensity, and quality. We present a new algorithm for feature finding which has been developed as a part of a combined experimental and algorithmic approach to absolutely quantify proteins from complex samples with unprecedented precision. The method was applied to the analysis of myoglobin in human blood serum, which is an important diagnostic marker for myocardial infarction. Our approach was able to determine the absolute amount of myoglobin in a serum sample through a series of standard addition experiments with a relative error of 2.5\%. It compares favorably to a manual analysis of the same data set since we could improve the precision and conduct the whole analysis pipeline in a small fraction of the time. We anticipate that our automatic quantitation method will facilitate further absolute or relative quantitation of even more complex peptide samples. The algorithm was implemented in the publicly available software framework OpenMS (www.OpenMS.de)
Cite as

Clemens Gröpl. An Algorithm for Feature Finding in LC/MS Raw Data. In Computational Proteomics. Dagstuhl Seminar Proceedings, Volume 5471, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{gropl:DagSemProc.05471.4,
  author =	{Gr\"{o}pl, Clemens},
  title =	{{An Algorithm for Feature Finding in LC/MS Raw Data}},
  booktitle =	{Computational Proteomics},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5471},
  editor =	{Christian G. Huber and Oliver Kohlbacher and Knut Reinert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05471.4},
  URN =		{urn:nbn:de:0030-drops-5341},
  doi =		{10.4230/DagSemProc.05471.4},
  annote =	{Keywords: Computational Proteomics, Quantitative Analysis, Liquid Chromatography, Mass Spectrometry, Algorithm, Software}
}
Document
DOI: 10.4230/DagSemProc.05471.5
Combinatorial Approaches for Mass Spectra Recalibration

Authors: Sebastian Böcker and Veli Mäkinen

Published in: Dagstuhl Seminar Proceedings, Volume 5471, Computational Proteomics (2006)

Abstract
Mass spectrometry has become one of the most popular analysis techniques in Proteomics and Systems Biology. With the creation of larger datasets, the automated recalibration of mass spectra becomes important to ensure that every peak in the sample spectrum is correctly assigned to some peptide and protein. Algorithms for recalibrating mass spectra have to be robust with respect to wrongly assigned peaks, as well as efficient due to the amount of mass spectrometry data. The recalibration of mass spectra leads us to the problem of finding an optimal matching between mass spectra under measurement errors. We have developed two deterministic methods that allow robust computation of such a matching: The first approach uses a computational geometry interpretation of the problem, and tries to find two parallel lines with constant distance that stab a maximal number of points in the plane. The second approach is based on finding a maximal common approximate subsequence, and improves existing algorithms by one order of magnitude exploiting the sequential nature of the matching problem. We compare our results to a computational geometry algorithm using a topological line-sweep.
Cite as

Sebastian Böcker and Veli Mäkinen. Combinatorial Approaches for Mass Spectra Recalibration. In Computational Proteomics. Dagstuhl Seminar Proceedings, Volume 5471, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{bocker_et_al:DagSemProc.05471.5,
  author =	{B\"{o}cker, Sebastian and M\"{a}kinen, Veli},
  title =	{{Combinatorial Approaches for Mass Spectra Recalibration}},
  booktitle =	{Computational Proteomics},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5471},
  editor =	{Christian G. Huber and Oliver Kohlbacher and Knut Reinert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05471.5},
  URN =		{urn:nbn:de:0030-drops-5455},
  doi =		{10.4230/DagSemProc.05471.5},
  annote =	{Keywords: Mass spectrometry recalibration computational geometry}
}
  • Refine by Author
  • 6 Huber, Christian G.
  • 6 Kohlbacher, Oliver
  • 4 Reinert, Knut
  • 3 Gröpl, Clemens
  • 2 Günther, Oliver
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Algorithmic game theory
  • Show More...

  • Refine by Keyword
  • 5 Proteomics
  • 5 mass spectrometry
  • 3 MALDI
  • 3 identification
  • 2 HPLC-MS
  • Show More...

  • Refine by Type
  • 25 document

  • Refine by Publication Year
  • 16 2006
  • 2 2008
  • 2 2022
  • 1 1999
  • 1 2011
  • Show More...

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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact