Packing cycles through prescribed vertices under modularity constraints |
| |
Authors: | Naonori Kakimura Ken-ichi Kawarabayashi |
| |
Affiliation: | 1. College of Arts and Sciences, University of Tokyo, Tokyo 153-8902, Japan;2. National Institute of Informatics, 2-1-2, Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan |
| |
Abstract: | The well-known theorem of Erd?s–Pósa says that either a graph G has k disjoint cycles or there is a vertex set X of order at most f(k) for some function f such that G?X is a forest. Starting with this result, there are many results concerning packing and covering cycles in graph theory and combinatorial optimization. |
| |
Keywords: | 05C70 05C38 68R10 |
本文献已被 ScienceDirect 等数据库收录! |
|