首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Packing cycles through prescribed vertices under modularity constraints
Authors:Naonori Kakimura  Ken-ichi Kawarabayashi
Institution: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)f(k) for some function f   such that G?XG?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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号