MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Properties of Connected f-Factors

C. S. Rahul
Indian Institute of Technology Madras, India
AG1 Mittagsseminar (own work)
AG 1, MMCI  
AG Audience
English

Date, Time and Location

Tuesday, 3 June 2014
13:00
30 Minutes
E1 4
024
Saarbrücken

Abstract

The problem of finding connected regular spanning subgraph

is shown to be NP-complete by Cheah and Corneil in 1990. This is basically an extension of the famous Hamiltonian cycle problem. Relaxing the regularity constraint leads to the connected f-factor problem. Given a graph G(V, E) and a function f : V → N, a connected f-factor of G is a connected spanning subgraph G′ such that d_G′(v)= f(v), ∀v ∈ V.
It is easy to extend the reduction by Cheah and Corneil to show that
connected f-factor problem is hard when the range of f is a fixed set.
We present the results on the how the complexity of, both the decision
and the optimization versions of the problem vary depending the nature
of f.

Contact

Andreas Wiese
--email hidden
passcode not visible
logged in users only

Andreas Wiese, 05/21/2014 16:42
Andreas Wiese, 05/21/2014 16:41 -- Created document.