2 papers
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…
cs.DS2024
Approximating Prize-Collecting Variants of TSP
Morteza Alimi, Tobias Mömke, Michael Ruderer
We present an approximation algorithm for the Prize-collecting Ordered Traveling Salesman Problem (PCOTSP), which simultaneously generalizes the Prize-collecting TSP and the Ordere…