A5063644073- Advanced Graph Theory Research
- Complexity and Algorithms in Graphs
- Algorithms and Data Compression
- Bioinformatics and Genomic Networks
- Data Management and Algorithms
- DNA and Biological Computing
- Genome Rearrangement Algorithms
- Gene Regulatory Network Analysis
- Optimization and Search Problems
- Microbial Metabolic Engineering and Bioproduction
- Interconnection Networks and Systems
- Genomics and Phylogenetic Studies
- Digital Image Processing Techniques
- Graph Labeling and Dimension Problems
- Genomics and Chromatin Dynamics
- Artificial Intelligence in Games
- Complex Network Analysis Techniques
- Computational Geometry and Mesh Generation
- Mathematical Approximation and Integration
- Graph Theory and Algorithms
- Constraint Satisfaction and Optimization
- graph theory and CDMA systems
- Microbial Natural Products and Biosynthesis
- semigroups and automata theory
- Model-Driven Software Engineering Techniques
TomTom (Germany)
2021
Technische Universität Berlin
2011-2020
Friedrich Schiller University Jena
2005-2016
Humboldt-Universität zu Berlin
2010-2011
Tel Aviv University
2009-2010
International Computer Science Institute
2009
University of Tübingen
2001-2004
To cover the edges of a graph with minimum number cliques is an NP-hard problem many applications. For this we develop efficient and effective polynomial-time data reduction rules that, combined search tree algorithm, allow for exact solutions in competitive time. This confirmed by experiments real-world synthetic data. Moreover, prove fixed-parameter tractability covering cliques.
In the network querying problem, one is given a protein complex or pathway of species A and protein–protein interaction B; goal to identify subnetworks B that are similar query in terms sequence, topology, both. Existing approaches mostly depend on knowledge topology A; however, practice, this often not known. To address we develop topology-free algorithm, which call Torque. Given query, represented as set proteins, Torque seeks matching proteins sequence-similar span connected region...
The fixed-parameter approach is an algorithm design technique for solving combinatorially hard (mostly NP-hard) problems. For some of these problems, it can lead to algorithms that are both efficient and yet at the same time guaranteed find optimal solutions. Focusing on their application NP-hard problems in practice, we survey three main techniques develop algorithms, namely: kernelization (data reduction with provable performance guarantee), depth-bounded search trees a new called...
To cover the edges of a graph with minimum number cliques is an NP-complete problem many applications. The state-of-the-art solving algorithm polynomial-time heuristic from 1970's. We present improvement this heuristic. Our main contribution, however, development efficient and effective data reduction rules that, combined search tree algorithm, allow for exact solutions in competitive time. This confirmed by experiments real-world synthetic data. Moreover, we prove fixed-parameter...
We examine exact algorithms for the NP-complete Graph Bipartization problem that asks a minimum set of vertices to delete from graph make it bipartite. Based on “iterative compression” method recently introduced by Reed, Smith, and Vetta, we present new experimental results. The worst-case time complexity is improved O(3k · kmn) mn), where n number vertices, m edges, k delete. Our best algorithm can solve all problems testbed computational biology within minutes, whereas established methods...
Torque is a tool for cross-species querying of protein–protein interaction networks. It aims to answer the following question: given set proteins constituting known complex or pathway in one species, can similar be found protein network another species? To this end, seeks matching that are sequence query and span connected region target network, while allowing both insertions deletions. Unlike existing approaches, does not require knowledge interconnections among proteins. handle large...
The core-periphery model for protein interaction (PPI) networks assumes that complexes in these consist of a dense core and possibly sparse periphery is adjacent to vertices the complex. In this work, we aim at uncovering global structure given PPI network. We propose two exact graph-theoretic formulations task, which fit input network hypothetical ground truth by minimum number edge modifications. one each cluster has its own periphery, other shared. first analyze both models from...