From the 1 of 6 linked papers with an AI index.
6 papers
Induced-Minor-Closed Classes have Linear, Square-Root, or Sub-Polynomial Tree-Independence
Maria Chudnovsky, Julien Codsi, Ajaykrishnan E S +1
The paper shows that any graph either contains a large complete bipartite graph or a large wall as an induced minor, or else its tree‑independence number grows sub‑polynomially, le…
Induced Minors and Coarse Tree Decompositions
Maria Chudnovsky, Julien Codsi, Ajaykrishnan E S +1
Let be a graph, be a vertex set in and be a positive integer. The distance -independence number of is the size of the largest subset $I \subse…
(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 $Ï: V(T) \rightarrow 2^{V(G)}…
Parameterized Approximation of Rectangle Stabbing
Huairui Chu, Ajaykrishnan E S, Daniel Lokshtanov +4
In the Rectangle Stabbing problem, input is a set of axis-parallel rectangles and a set of axis parallel lines in the plane. The task is to find a minimum siz…
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…
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…