6 Search Results for "H�ndling, Jens"


Document
A Linear Time Algorithm for an Extended Version of the Breakpoint Double Distance

Authors: Marília D. V. Braga, Leonie R. Brockmann, Katharina Klerx, and Jens Stoye

Published in: LIPIcs, Volume 242, 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022)


Abstract
Two genomes over the same set of gene families form a canonical pair when each of them has exactly one gene from each family. A genome is circular when it contains only circular chromosomes. Different distances of canonical circular genomes can be derived from a structure called breakpoint graph, which represents the relation between the two given genomes as a collection of cycles of even length. Then, the breakpoint distance is equal to n-c_2, where n is the number of genes and c_2 is the number of cycles of length 2. Similarly, when the considered rearrangements are those modeled by the double-cut-and-join (DCJ) operation, the rearrangement distance is n-c, where c is the total number of cycles. The distance problem is a basic unit for several other combinatorial problems related to genome evolution and ancestral reconstruction, such as median or double distance. Interestingly, both median and double distance problems can be solved in polynomial time for the breakpoint distance, while they are NP-hard for the rearrangement distance. One way of exploring the complexity space between these two extremes is to consider a σ_k distance, defined to be n-(c_2+c_4+…+c_k), and increasingly investigate the complexities of median and double distance for the σ₄ distance, then the σ₆ distance, and so on. While for the median much effort was done in our and in other research groups but no progress was obtained even for the σ₄ distance, for solving the double distance under σ₄ and σ₆ distances we could devise linear time algorithms, which we present here.

Cite as

Marília D. V. Braga, Leonie R. Brockmann, Katharina Klerx, and Jens Stoye. A Linear Time Algorithm for an Extended Version of the Breakpoint Double Distance. In 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 242, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{braga_et_al:LIPIcs.WABI.2022.13,
  author =	{Braga, Mar{\'\i}lia D. V. and Brockmann, Leonie R. and Klerx, Katharina and Stoye, Jens},
  title =	{{A Linear Time Algorithm for an Extended Version of the Breakpoint Double Distance}},
  booktitle =	{22nd International Workshop on Algorithms in Bioinformatics (WABI 2022)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-243-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{242},
  editor =	{Boucher, Christina and Rahmann, Sven},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2022.13},
  URN =		{urn:nbn:de:0030-drops-170472},
  doi =		{10.4230/LIPIcs.WABI.2022.13},
  annote =	{Keywords: Comparative genomics, genome rearrangement, breakpoint distance, double-cut-and-join (DCJ) distance, double distance}
}
Document
Local Certification of Graph Decompositions and Applications to Minor-Free Classes

Authors: Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)


Abstract
Local certification consists in assigning labels to the nodes of a network to certify that some given property is satisfied, in such a way that the labels can be checked locally. In the last few years, certification of graph classes received a considerable attention. The goal is to certify that a graph G belongs to a given graph class 𝒢. Such certifications with labels of size O(log n) (where n is the size of the network) exist for trees, planar graphs and graphs embedded on surfaces. Feuilloley et al. ask if this can be extended to any class of graphs defined by a finite set of forbidden minors. In this work, we develop new decomposition tools for graph certification, and apply them to show that for every small enough minor H, H-minor-free graphs can indeed be certified with labels of size O(log n). We also show matching lower bounds using a new proof technique.

Cite as

Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron. Local Certification of Graph Decompositions and Applications to Minor-Free Classes. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.OPODIS.2021.22,
  author =	{Bousquet, Nicolas and Feuilloley, Laurent and Pierron, Th\'{e}o},
  title =	{{Local Certification of Graph Decompositions and Applications to Minor-Free Classes}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{22:1--22:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.22},
  URN =		{urn:nbn:de:0030-drops-157970},
  doi =		{10.4230/LIPIcs.OPODIS.2021.22},
  annote =	{Keywords: Local certification, proof-labeling schemes, locally checkable proofs, graph decompositions, minor-free graphs}
}
Document
Construction Sequences and Certifying 3-Connectedness

Authors: Jens M. Schmidt

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)


Abstract
Given two $3$-connected graphs $G$ and $H$, a \emph{construction sequence} constructs $G$ from $H$ (e.\,g. from the $K_4$) with three basic operations, called the \emph{Barnette-Gr\"unbaum operations}. These operations are known to be able to construct all $3$-connected graphs. We extend this result by identifying every intermediate graph in the construction sequence with a subdivision in $G$ and showing under some minor assumptions that there is still a construction sequence to $G$ when we start from an \emph{arbitrary prescribed} $H$-subdivision. This leads to the first algorithm that computes a construction sequence in time $O(|V(G)|^2)$. As an application, we develop a certificate for the $3$-connectedness of graphs that can be easily computed and verified. Based on this, a certifying test on $3$-connectedness is designed.%Finding certifying algorithms is a major goal for problems where the efficient solutions known are complicated. Tutte proved that every $3$-connected graph on more than $4$ nodes has a \emph{contractible edge}. Barnette and Gr\"unbaum proved the existence of a \emph{removable edge} in the same setting. We show that the sequence of contractions and the sequence of removals from $G$ to the $K_4$ can be computed in $O(|V|^2)$ time by extending Barnette and Gr\"unbaum's theorem. As an application, we derive a certificate for the $3$-connectedness of graphs that can be easily computed and verified.

Cite as

Jens M. Schmidt. Construction Sequences and Certifying 3-Connectedness. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 633-644, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{schmidt:LIPIcs.STACS.2010.2491,
  author =	{Schmidt, Jens M.},
  title =	{{Construction Sequences and Certifying 3-Connectedness}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{633--644},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2491},
  URN =		{urn:nbn:de:0030-drops-24918},
  doi =		{10.4230/LIPIcs.STACS.2010.2491},
  annote =	{Keywords: Construction sequence, 3-connected graph, nested subdivisions, inductive characterization, 3-connectedness, certifying algorithm}
}
Document
Integrated Vehicle Routing and Crew Scheduling in Waste Management (Part II)

Authors: Jens Baudach, Annette Chmielewski, and Uwe Clausen

Published in: Dagstuhl Seminar Proceedings, Volume 9261, Models and Algorithms for Optimization in Logistics (2009)


Abstract
Planning Waste Management involves the two major resources collection-vehicles and crews. The overall goal of our project with two waste management companies is an integrative approach for planning the routes and the crews of the vehicles. In the first phase of our three-phase approach we generate daily crew tasks which contain routes operated by a single crew at a particular day within a given disposal horizon considering various practical requirements. The goal is to minimize the number of crews/vehicles required for the entire disposal process. Given the minimal number of crews, in phase 2 we re-optimize the daily crew tasks to increase the robustness of the routes. In the third phase we assign employees to the generated daily crew tasks for all working days over the year such that the constraints concerning crew scheduling are satisfied and the benefits for the employees and the company are maximal. For all phases we present solution methods yielding first promising results for a real-world data set.

Cite as

Jens Baudach, Annette Chmielewski, and Uwe Clausen. Integrated Vehicle Routing and Crew Scheduling in Waste Management (Part II). In Models and Algorithms for Optimization in Logistics. Dagstuhl Seminar Proceedings, Volume 9261, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{baudach_et_al:DagSemProc.09261.14,
  author =	{Baudach, Jens and Chmielewski, Annette and Clausen, Uwe},
  title =	{{Integrated Vehicle Routing and Crew Scheduling in Waste Management (Part II)}},
  booktitle =	{Models and Algorithms for Optimization in Logistics},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9261},
  editor =	{Cynthia Barnhart and Uwe Clausen and Ulrich Lauther and Rolf H. M\"{o}hring},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09261.14},
  URN =		{urn:nbn:de:0030-drops-21836},
  doi =		{10.4230/DagSemProc.09261.14},
  annote =	{Keywords: Crew Scheduling, Waste Management, Integer Programming, Column Generation, Lagrangean Relaxation}
}
Document
2. 08102 Working Group – Early Warning Systems

Authors: Joachim Biskup, Bernhard Hämmerli, Michael Meier, Sebastian Schmerl, Jens Tölle, and Michael Vogel

Published in: Dagstuhl Seminar Proceedings, Volume 8102, Perspectives Workshop: Network Attack Detection and Defense (2008)


Abstract
Early Warning Systems aim at detecting unclassified but potentially harmful sys-tem behavior based on preliminary indications and are complementary to Intrusion Detection Systems. Both kinds of systems try to detect, identify and react before pos-sible damage occurs and contribute to an integrated and aggregated situation report (big picture). A particular emphasis of Early Warning Systems is to establish hypotheses and predictions as well as to generate advises in still not completely understood situations. Thus the term early has two meanings, a) to start early in time aiming to minimize damage, and b) to process uncertain and incomplete information.

Cite as

Joachim Biskup, Bernhard Hämmerli, Michael Meier, Sebastian Schmerl, Jens Tölle, and Michael Vogel. 2. 08102 Working Group – Early Warning Systems. In Perspectives Workshop: Network Attack Detection and Defense. Dagstuhl Seminar Proceedings, Volume 8102, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{biskup_et_al:DagSemProc.08102.2,
  author =	{Biskup, Joachim and H\"{a}mmerli, Bernhard and Meier, Michael and Schmerl, Sebastian and T\"{o}lle, Jens and Vogel, Michael},
  title =	{{2. 08102 Working Group – Early Warning Systems}},
  booktitle =	{Perspectives Workshop: Network Attack Detection and Defense},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8102},
  editor =	{Georg Carle and Falko Dressler and Richard A. Kemmerer and Hartmut K\"{o}nig and Christopher Kruegel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08102.2},
  URN =		{urn:nbn:de:0030-drops-14936},
  doi =		{10.4230/DagSemProc.08102.2},
  annote =	{Keywords: Intrusion detection and prevention, attack response and countermeasures, reactive security, automated security, survivability and self-protection, ma network monitoring, flow analysis, denial of service detection and response, event correlation}
}
Document
Towards A Meta-Model for Service Properties

Authors: Jens Hündling

Published in: Dagstuhl Seminar Proceedings, Volume 5462, Service Oriented Computing (SOC) (2006)


Abstract
Service Oriented Computing offers a promising approach for global businesses and integrated, virtual enterprises that achieve common business goals. For realizing an exhaustive Service Oriented Architecture, some basic research is still necessary and a consensus has to be reached about key aspects. We argue that a key aspect is a common model for enriched service descriptions, especially for all use cases related to service discovery. For automated discovery, these service descriptions need to be specified in a formal, computer-readable way. Additionally, properties of services that are beyond technical interface specifications should be modelled, e.g. by including Quality of Service (QoS) properties.

Cite as

Jens Hündling. Towards A Meta-Model for Service Properties. In Service Oriented Computing (SOC). Dagstuhl Seminar Proceedings, Volume 5462, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{hundling:DagSemProc.05462.9,
  author =	{H\"{u}ndling, Jens},
  title =	{{Towards A Meta-Model for Service Properties}},
  booktitle =	{Service Oriented Computing (SOC)},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5462},
  editor =	{Francisco Cubera and Bernd J. Kr\"{a}mer and Michael P. Papazoglou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05462.9},
  URN =		{urn:nbn:de:0030-drops-5295},
  doi =		{10.4230/DagSemProc.05462.9},
  annote =	{Keywords: Service Properties, Quality of Services, QoS, non-functional Properties, Service Discovery}
}
  • Refine by Author
  • 1 Baudach, Jens
  • 1 Biskup, Joachim
  • 1 Bousquet, Nicolas
  • 1 Braga, Marília D. V.
  • 1 Brockmann, Leonie R.
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Bioinformatics
  • 1 Theory of computation → Distributed algorithms

  • Refine by Keyword
  • 1 3-connected graph
  • 1 3-connectedness
  • 1 Column Generation
  • 1 Comparative genomics
  • 1 Construction sequence
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2022
  • 1 2006
  • 1 2008
  • 1 2009
  • 1 2010

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