11 papers
A King for Almost Everyone
Ziad Ismaili Alaoui, Oded Lachish, Nikhil S. Mande
A tournament is an orientation of a complete graph. A vertex controls a vertex if there is a directed path of length at most two from to , and a -king is on…
Directed Cut-Query Complexity of Finding a King
Ziad Ismaili Alaoui, Oded Lachish, Nikhil S. Mande
A king in a tournament is a vertex from which every other vertex is reachable by a directed path of length at most two. We study the deterministic query complexity of finding a kin…
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 …
Independent Set Reconfiguration via Dilworth Decompositions
Ziad Ismaili Alaoui
The Token Jumping and Sliding Token problems are fundamental reconfiguration problems defined on the independent sets of an undirected graph. Given two independent sets and …
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…
Implementing Binary Search Trees in GP 2 (Extended Abstract)
Ziad Ismaili Alaoui, Detlef Plump
We present an approach to implement binary search trees in the rule-based graph programming language GP 2. Our implementation uses GP 2's rooted graph transformation rules to be fa…
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…
Hardness of Finding Kings and Strong Kings
Ziad Ismaili Alaoui, Nikhil S. Mande
A king in a directed graph is a vertex such that every other vertex is reachable from via a path of length at most . It is well known that every tournament (a complete g…
Linear-Time Graph Programs without Preconditions
Ziad Ismaili Alaoui, Detlef Plump
We report on a recent breakthrough in rule-based graph programming, which allows us to reach the time complexity of imperative linear-time algorithms. In general, achieving the com…
Rule-Based Graph Programs Matching the Time Complexity of Imperative Algorithms
Ziad Ismaili Alaoui, Detlef Plump
We report on recent advances in rule-based graph programming, which allow us to match the time complexity of some fundamental imperative graph algorithms. In general, achieving the…