4 Search Results for "Hung, Chien-Wen"

Document
DOI: 10.4230/LIPIcs.ISAAC.2018.27
New and Improved Algorithms for Unordered Tree Inclusion

Authors: Tatsuya Akutsu, Jesper Jansson, Ruiming Li, Atsuhiro Takasu, and Takeyuki Tamura

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
The tree inclusion problem is, given two node-labeled trees P and T (the "pattern tree" and the "text tree"), to locate every minimal subtree in T (if any) that can be obtained by applying a sequence of node insertion operations to P. Although the ordered tree inclusion problem is solvable in polynomial time, the unordered tree inclusion problem is NP-hard. The currently fastest algorithm for the latter is from 1995 and runs in O(poly(m,n) * 2^{2d}) = O^*(2^{2d}) time, where m and n are the sizes of the pattern and text trees, respectively, and d is the maximum outdegree of the pattern tree. Here, we develop a new algorithm that improves the exponent 2d to d by considering a particular type of ancestor-descendant relationships and applying dynamic programming, thus reducing the time complexity to O^*(2^d). We then study restricted variants of the unordered tree inclusion problem where the number of occurrences of different node labels and/or the input trees' heights are bounded. We show that although the problem remains NP-hard in many such cases, it can be solved in polynomial time for c = 2 and in O^*(1.8^d) time for c = 3 if the leaves of P are distinctly labeled and each label occurs at most c times in T. We also present a randomized O^*(1.883^d)-time algorithm for the case that the heights of P and T are one and two, respectively.
Cite as

Tatsuya Akutsu, Jesper Jansson, Ruiming Li, Atsuhiro Takasu, and Takeyuki Tamura. New and Improved Algorithms for Unordered Tree Inclusion. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 27:1-27:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{akutsu_et_al:LIPIcs.ISAAC.2018.27,
  author =	{Akutsu, Tatsuya and Jansson, Jesper and Li, Ruiming and Takasu, Atsuhiro and Tamura, Takeyuki},
  title =	{{New and Improved Algorithms for Unordered Tree Inclusion}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{27:1--27:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.27},
  URN =		{urn:nbn:de:0030-drops-99752},
  doi =		{10.4230/LIPIcs.ISAAC.2018.27},
  annote =	{Keywords: parameterized algorithms, tree inclusion, unordered trees, dynamic programming}
}
Document
DOI: 10.4230/LITES-v005-i001-a002
Errata for Three Papers (2004-05) on Fixed-Priority Scheduling with Self-Suspensions

Authors: Konstantinos Bletsas, Neil C. Audsley, Wen-Hung Huang, Jian-Jia Chen, and Geoffrey Nelissen

Published in: LITES, Volume 5, Issue 1 (2018). Leibniz Transactions on Embedded Systems, Volume 5, Issue 1

Abstract
The purpose of this article is to (i) highlight the flaws in three previously published works [Audsley, 2004a; Audsley, 2004b; Bletsas, 2005] on the worst-case response time analysis for tasks with self-suspensions and (ii) provide straightforward fixes for those flaws, hence rendering the analysis safe.
Cite as

Konstantinos Bletsas, Neil C. Audsley, Wen-Hung Huang, Jian-Jia Chen, and Geoffrey Nelissen. Errata for Three Papers (2004-05) on Fixed-Priority Scheduling with Self-Suspensions. In LITES, Volume 5, Issue 1 (2018). Leibniz Transactions on Embedded Systems, Volume 5, Issue 1, pp. 02:1-02:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{bletsas_et_al:LITES-v005-i001-a002,
  author =	{Bletsas, Konstantinos and Audsley, Neil C. and Huang, Wen-Hung and Chen, Jian-Jia and Nelissen, Geoffrey},
  title =	{{Errata for Three Papers (2004-05) on Fixed-Priority Scheduling with Self-Suspensions}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{02:1--02:20},
  ISSN =	{2199-2002},
  year =	{2018},
  volume =	{5},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LITES-v005-i001-a002},
  doi =		{10.4230/LITES-v005-i001-a002},
  annote =	{Keywords: real-time, scheduling, self-suspension, worst-case response time analysis}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2017.9
On the Pitfalls of Resource Augmentation Factors and Utilization Bounds in Real-Time Scheduling

Authors: Jian-Jia Chen, Georg von der Brüggen, Wen-Hung Huang, and Robert I. Davis

Published in: LIPIcs, Volume 76, 29th Euromicro Conference on Real-Time Systems (ECRTS 2017)

Abstract
In this paper, we take a careful look at speedup factors, utilization bounds, and capacity augmentation bounds. These three metrics have been widely adopted in real-time scheduling research as the de facto standard theoretical tools for assessing scheduling algorithms and schedulability tests. Despite that, it is not always clear how researchers and designers should interpret or use these metrics. In studying this area, we found a number of surprising results, and related to them, ways in which the metrics may be misinterpreted or misunderstood. In this paper, we provide a perspective on the use of these metrics, guiding researchers on their meaning and interpretation, and helping to avoid pitfalls in their use. Finally, we propose and demonstrate the use of parametric augmentation functions as a means of providing nuanced information that may be more relevant in practical settings.
Cite as

Jian-Jia Chen, Georg von der Brüggen, Wen-Hung Huang, and Robert I. Davis. On the Pitfalls of Resource Augmentation Factors and Utilization Bounds in Real-Time Scheduling. In 29th Euromicro Conference on Real-Time Systems (ECRTS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 76, pp. 9:1-9:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ECRTS.2017.9,
  author =	{Chen, Jian-Jia and von der Br\"{u}ggen, Georg and Huang, Wen-Hung and Davis, Robert I.},
  title =	{{On the Pitfalls of Resource Augmentation Factors and Utilization Bounds in Real-Time Scheduling}},
  booktitle =	{29th Euromicro Conference on Real-Time Systems (ECRTS 2017)},
  pages =	{9:1--9:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-037-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{76},
  editor =	{Bertogna, Marko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2017.9},
  URN =		{urn:nbn:de:0030-drops-71619},
  doi =		{10.4230/LIPIcs.ECRTS.2017.9},
  annote =	{Keywords: Real-time systems, speedup factors, utilization bounds, capacity augmentation bounds}
}
Document
DOI: 10.4230/OASIcs.GCB.2013.56
Efficient Interpretation of Tandem Mass Tags in Top-Down Proteomics

Authors: Anna Katharina Hildebrandt, Ernst Althaus, Hans-Peter Lenhof, Chien-Wen Hung, Andreas Tholey, and Andreas Hildebrandt

Published in: OASIcs, Volume 34, German Conference on Bioinformatics 2013

Abstract
Mass spectrometry is the major analytical tool for the identification and quantification of proteins in biological samples. In so-called top-down proteomics, separation and mass spectrometric analysis is performed at the level of intact proteins, without preparatory digestion steps. It has been shown that the tandem mass tag (TMT) labeling technology, which is often used for quantification based on digested proteins (bottom-up studies), can be applied in top-down proteomics as well. This, however, leads to a complex interpretation problem, where we need to annotate measured peaks with their respective generating protein, the number of charges, and the a priori unknown number of TMT-groups attached to this protein. In this work, we give an algorithm for the efficient enumeration of all valid annotations that fulfill available experimental constraints. Applying the algorithm to real-world data, we show that the annotation problem can indeed be efficiently solved. However, our experiments also demonstrate that reliable annotation in complex mixtures requires at least partial sequence information and high mass accuracy and resolution to go beyond the proof-of-concept stage.
Cite as

Anna Katharina Hildebrandt, Ernst Althaus, Hans-Peter Lenhof, Chien-Wen Hung, Andreas Tholey, and Andreas Hildebrandt. Efficient Interpretation of Tandem Mass Tags in Top-Down Proteomics. In German Conference on Bioinformatics 2013. Open Access Series in Informatics (OASIcs), Volume 34, pp. 56-67, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{hildebrandt_et_al:OASIcs.GCB.2013.56,
  author =	{Hildebrandt, Anna Katharina and Althaus, Ernst and Lenhof, Hans-Peter and Hung, Chien-Wen and Tholey, Andreas and Hildebrandt, Andreas},
  title =	{{Efficient Interpretation of Tandem Mass Tags in Top-Down Proteomics}},
  booktitle =	{German Conference on Bioinformatics 2013},
  pages =	{56--67},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-59-0},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{34},
  editor =	{Bei{\ss}barth, Tim and Kollmar, Martin and Leha, Andreas and Morgenstern, Burkhard and Schultz, Anne-Kathrin and Waack, Stephan and Wingender, Edgar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.GCB.2013.56},
  URN =		{urn:nbn:de:0030-drops-42304},
  doi =		{10.4230/OASIcs.GCB.2013.56},
  annote =	{Keywords: Mass spectrometry, TMT labeling, Top-down Proteomics}
}
  • Refine by Author
  • 2 Chen, Jian-Jia
  • 2 Huang, Wen-Hung
  • 1 Akutsu, Tatsuya
  • 1 Althaus, Ernst
  • 1 Audsley, Neil C.
  • Show More...

  • Refine by Classification
  • 1 Computer systems organization → Embedded systems
  • 1 Computer systems organization → Real-time systems
  • 1 Software and its engineering → Real-time schedulability
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 Mass spectrometry
  • 1 Real-time systems
  • 1 TMT labeling
  • 1 Top-down Proteomics
  • 1 capacity augmentation bounds
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2018
  • 1 2013
  • 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact