1 citations · 1 across the 5 of their papers we have counts for
7 papers
Enumerating tuples of spanning trees
Rahul CS, Michal Wlodarczyk
Deciding whether a graph has k-edge-disjoint spanning trees is a well-studied problem. We consider the problem of enumerating all sets of spanning trees with polynomial delay. This…
Graph Homomorphism Polynomials: Algorithms and Complexity
Balagopal Komarath, Anurag Pandey, C. S. Rahul
We study homomorphism polynomials, which are polynomials that enumerate all homomorphisms from a pattern graph to -vertex graphs. These polynomials have received a lot of at…
On the Complexity Landscape of Connected f -Factor Problems
R. Ganian, N. S. Narayanaswamy, S. Ordyniak +2
Let G be an undirected simple graph having n vertices and let f be a function defined to be f:V(G) -> {0,..., n-1}. An f-factor of G is a spanning subgraph H such that degree of a…
Group Activity Selection with Few Agent Types
Robert Ganian, Sebastian Ordyniak, C. S. Rahul
The Group Activity Selection Problem (GASP) models situations where a group of agents needs to be distributed to a set of activities while taking into account preferences of the ag…
A Characterization for the Existence of Connected -Factors of Minimum Degree
N S Narayanaswamy, C S Rahul
It is well known that when is a constant for each vertex , the connected -factor problem is NP-Complete. In this note we consider the case when $f(v) \geq \lceil \frac…
A Classification of Connected f -factor Problems inside NP
N. S. Narayanaswamy, C. S. Rahul
Given an undirected graph G = (V, E) with n vertices, and a function f : V -> N, we consider the problem of finding a connected f -factor in G. In this work we design an algorithm…
Approximability of Connected Factors
Kamiel Cornelissen, Ruben Hoeksma, Bodo Manthey +2
Finding a d-regular spanning subgraph (or d-factor) of a graph is easy by Tutte's reduction to the matching problem. By the same reduction, it is easy to find a minimal or maximal…