Given a graph G, and positive integers k, q, pack the edges of G in (pairwise edge disjoint) connected sub-graphs, each of size (number of edges) at most k, and such that, no vertex is part of more than q of these connected sub-graphs.

What is the closet related problem already studied? What can be said in case we restrict to k=3, q=2, and graphs of maximum degree 3?

  • 1
    $\begingroup$ This sounds like homework, where did you get stuck? $\endgroup$
    – Pål GD
    Jul 8 '15 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.