5 papers
Clustering with Set Outliers and Applications in Relational Clustering
Vaishali Surianarayanan, Neeraj Kumar, Stavros Sintos
We introduce and study the -center clustering problem with set outliers, a natural and practical generalization of the classical -center clustering with outliers. Instead of…
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…
Linear Layouts Revisited: Stacks, Queues, and Exact Algorithms
Thomas Depian, Simon D. Fink, Robert Ganian +1
In spite of the extensive study of stack and queue layouts, many fundamental questions remain open concerning the complexity-theoretic frontiers for computing stack and queue layou…
Parameterized Approximation for Capacitated -Hitting Set with Hard Capacities
Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh +2
The \textsc{Capacitated -Hitting Set} problem involves a universe with a capacity function and a collection of subsets…
Efficient Approximation of Fractional Hypertree Width
Viktoriia Korchemna, Daniel Lokshtanov, Saket Saurabh +2
We give two new approximation algorithms to compute the fractional hypertree width of an input hypergraph. The first algorithm takes as input -vertex -edge hypergraph of…