6 papers
Space-Efficient Hierholzer for Undirected Graphs
Elena Grigorescu, Ziad Ismaili Alaoui, Tamio-Vesa Nakajima +2
We present a simple linear-time algorithm that outputs an Eulerian tour of an undirected multigraph with vertices and edges, if one exists, in time and using …
Rooting Out Entropy: Optimal Tree Extraction for Ultra-Succinct Graphs
Ziad Ismaili Alaoui, Tamio-Vesa Nakajima, Namrata +1
We combine two methods for the lossless compression of unlabeled graphs - entropy compressing adjacency lists and computing canonical names for vertices - and solve an ensuing nove…
Space-Efficient Hierholzer: Eulerian Cycles in Time and Space
Ziad Ismaili Alaoui, Detlef Plump, Sebastian Wild
We describe a simple variant of Hierholzer's algorithm that finds an Eulerian cycle in a directed (multi)graph with vertices and edges using bits of w…
Succinct Preferential Attachment Graphs
Ziad Ismaili Alaoui, Namrata, Sebastian Wild
Computing over compressed data combines the space saving of data compression with efficient support for queries directly on the compressed representation. Such data structures are…
Simple approximation algorithms for Polyamorous Scheduling
Yuriy Biktairov, Leszek Gąsieniec, Wanchote Po Jiamjitrak +3
In Polyamorous Scheduling, we are given an edge-weighted graph and must find a periodic schedule of matchings in this graph which minimizes the maximal weighted waiting time betwee…
Polyamorous Scheduling
Leszek Gąsieniec, Benjamin Smith, Sebastian Wild
Finding schedules for pairwise meetings between the members of a complex social group without creating interpersonal conflict is challenging, especially when different relationship…