2 papers
cs.DS2025
Polynomial-time algorithms for PATH COVER and PATH PARTITION on trees and graphs of bounded treewidth
Florent Foucaud, Atrayee Majumder, Tobias Mömke +1
In the PATH COVER problem, one asks to cover the vertices of a graph using the smallest possible number of (not necessarily disjoint) paths. While the variant where the paths need…
cs.DM2025
Approximating Maximum Edge 2-Coloring by Normalizing Graphs
Tobias Mömke, Alexandru Popa, Aida Roshany-Tabrizi +2
In a simple, undirected graph G, an edge 2-coloring is a coloring of the edges such that no vertex is incident to edges with more than 2 distinct colors. The problem maximum edge 2…