121 citations · 373 across the 96 of their papers we have counts for
8 papers · 1 filter
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…
Induced minors and subpolynomial treewidth
Maria Chudnovsky, Julien Codsi, David Fischer +1
Given a family of graphs, we say that a graph is -induced-minor-free if no induced minor of is isomorphic to a member of , We denote…
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…
(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 …
Path Contraction Faster than
Akanksha Agrawal, Fedor V. Fomin, Daniel Lokshtanov +2
A graph is contractible to a graph if there is a set , such that is isomorphic to . Here, is the graph obtained from by contracting all…
A Quadratic Vertex Kernel and a Subexponential Algorithm for Subset-FAST
Satyabrata Jana, Lawqueen Kanesh, Madhumita Kundu +2
In the Subset Feedback Arc Set in Tournaments, Subset-FAST problem we are given as input a tournament with a vertex set and an arc set , along with a terminal set…
Tree independence number V. Walls and claws
Maria Chudnovsky, Julien Codsi, Daniel Lokshtanov +2
Given a family of graphs, we say that a graph is -free if no induced subgraph of is isomorphic to a member of . Let be t…
Sampling Unlabeled Chordal Graphs in Expected Polynomial Time
Úrsula Hébert-Johnson, Daniel Lokshtanov
We design an algorithm that generates an -vertex unlabeled chordal graph uniformly at random in expected polynomial time. Along the way, we develop the following two results: (1…