Showing 2025Show all
3 papers · 1 filter
cs.DS2025
Beyond Exact Fairness: Envy-Free Incomplete Connected Fair Division
Ajaykrishnan E S, Daniel Lokshtanov
We study the problem of Envy-Free Incomplete Connected Fair Division, where exactly p vertices of an undirected graph must be allocated to agents such that each agent receives a co…
cs.DS2025
A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs
Ajaykrishnan E S, Robert Ganian, Daniel Lokshtanov +1
A graph is a circle graph if it is an intersection graph of chords of a unit circle. We give an algorithm that takes as input an vertex circle graph , runs in time at mo…
math.CO2025
(Treewidth, Clique)-Boundedness and Poly-logarithmic Tree-Independence
Maria Chudnovsky, Ajaykrishnan E S, Daniel Lokshtanov
An independent set in a graph is a set of pairwise non-adjacent vertices. A tree decomposition of is a pair where is a tree and …