Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SANJANA KOLISETTY:
All reports by Author Sanjana Kolisetty:

TR19-040 | 19th February 2019
Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis

The Complexity of Finding {$S$}-factors in Regular Graphs

A graph $G$ has an \emph{$S$-factor} if there exists a spanning subgraph $F$ of $G$ such that for all $v \in V: \deg_F(v) \in S$.
The simplest example of such factor is a $1$-factor, which corresponds to a perfect matching in a graph. In this paper we study the computational ... more >>>




ISSN 1433-8092 | Imprint