Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR19-040 | 19th February 2019 18:37

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

RSS-Feed

Abstract:

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 complexity of finding S-factors in regular graphs.
Our techniques combine some classical as well as recent tools from graph theory.



ISSN 1433-8092 | Imprint