Events Detail

Speaker:
Mahsa Mozafary und Anteneh Getachew, ZUKOnnect and Herz Fellows, University of Konstanz

Mahsa Mozafary: Bounds for the Path Vertex Cover Problem via Graph Coloring

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. In this context, the objects are called nodes or vertices and the relations are represented as lines (also called edges). Extremal graph theory as a branch of graph theory is studying some properties of graphs. One of the goals is to identify lower or upper bounds for a given property. In this research project, we are going to improve known lower and upper bounds for the k-path vertex cover problem by considering certain types of graph coloring. Graph coloring is a concept in extremal graph theory in which we assign (color) labels to vertices of the graph subject to some constraints, for example, that no two vertices connected with an edge share the same color. In the k-path vertex cover problem, the goal is covering all paths of length k or more in a given graph using a concise subset of vertices. The size of the smallest set with this property is called the k-path vertex cover number of the graph. The k-path vertex cover problem is a generalization of the classical vertex cover problem and naturally inherits its hardness. However, it is likely that the problem is even harder to approximate than the vertex cover special case. Star coloring and defective coloring are two types of vertex coloring that appear to be connected to the concept of path vertex cover problems. We are investigating these colorings on certain graph classes to learn more about the relationships between those two problems. Moreover, we are looking for path vertex cover number of special graphs such as Kneser graphs KG(n, r). So far we have found the exact k-path vertex cover number of KG(n, 2).

Mahsa Mozafary is a Zukunftskolleg Herz Fellow at the University of Konstanz

Anteneh Getachew Gebrie: Decentralized accelerated algorithms for hierarchical optimization problems

The purpose of the research work is to introduce accelerated algorithms using the proximal conjugate gradient method for distributed constrained optimizations given as minimization of a function decomposed as a sum of M number of functions over the common fixed points of M number of nonlinear mappings. Exploiting the special structure of the each cost component functions of the objective function and each nonlinear mapping of the constraint problem, we present two new inertial accelerated algorithms, incremental and parallel computation type algorithms, involving combinations of proximal, conjugate gradient and Halpern iteration methods. Some numerical experiments and comparisons are given to illustrate our results.

Anteneh Getachew Gebrie is ZUKOnnect Fellow at the University of Konstanz

Join the meeting online

The Zukunftskolleg Konnect and Herz Fellowships support early career researchers from Africa, Asia and Latin America who are associated with one of the thirteen departments or the clusters of excellence at the University of Konstanz. As a ZUKOnnect or Herz Fellow, you can use this time to extend your research networks and to get to know the research environment at the University of Konstanz while keeping your position at home. As these fellowships can build a first bridge to the German and European academic system, we also encourage doctoral students in their last year to apply. The ZUKOnnect Fellowships are awarded in an open application process that require no prior connection to the university. The Herz Fellowship, in difference, rely on previous research contacts to the university and are awarded  upon nomination by (junior) professors of the University of Konstanz. Both fellowship entail an up to 4-month research stay at the University of Konstanz and a digital affiliation for 12 months.