6 papers
Exact Joint MAP Decoding for Unknown Load and Message Counts in Orthogonal Unsourced Random Access
Mohammad Kazemi, Mert Ozates
We study joint recovery of the load (the number of active users) and message-count vector in type-based unsourced random access with very short messages. Each user's -bit messag…
Structural Complexity of Matching-Match: Dense and Sparse Graphs
Ilie Dumitru, Adrian Miclăuş, Alexandru Popa
The Matching-Match puzzle asks whether the vertices of a fixed graph can be colored so that the multiset of color pairs induced by its edges is exactly a prescribed multiset. We st…
An Approximation Algorithm for Non-uniform Non-contiguous Translocation Distance
Maria Constantin, Adrian Miclăuş, Alexandru Popa
Translocations are genome rearrangement operations that exchange prefixes of two chromosomes. We study the non-uniform non-contiguous translocation distance problem, where every st…
Colored Interaction-Profile Realization: Complexity of Matching-Match on Spiders
Ilie Dumitru, Adrian Miclaus, Alexandru Popa
Network motifs and colored local interaction patterns provide a useful way to describe the structure of complex networks. Motivated by an inverse realization perspective, we study…
Maximum Matching-Match: Hardness and Approximation
Ilie Dumitru, Adrian Miclăuş, Alexandru Popa
In this paper, we study \textsc{MaxMMP}, an optimization variant of the Matching-Match Puzzle introduced by Iburi and Uehara (FUN 2024). Given a graph, a partial vertex coloring, a…
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…