Cores are, besides connectivity components, one among few concepts that provides us with efficient decompositions of large graphs and networks.
In the paper a generalization of the notion of core of a graph based on vertex property function is presented. It is shown that for the local monotone vertex property functions the corresponding cores can be determined in $O(m (\Delta, n))$ time.
%0 Generic
%1 batagelj-2002
%A Batagelj, V.
%A Zaversnik, M.
%D 2002
%K core generalized graph kern p reduction subgraph
%T Generalized Cores
%U http://arxiv.org/ps/cs/0202039
%X Cores are, besides connectivity components, one among few concepts that provides us with efficient decompositions of large graphs and networks.
In the paper a generalization of the notion of core of a graph based on vertex property function is presented. It is shown that for the local monotone vertex property functions the corresponding cores can be determined in $O(m (\Delta, n))$ time.
@misc{batagelj-2002,
abstract = {Cores are, besides connectivity components, one among few concepts that provides us with efficient decompositions of large graphs and networks.
In the paper a generalization of the notion of core of a graph based on vertex property function is presented. It is shown that for the local monotone vertex property functions the corresponding cores can be determined in $O(m \max (\Delta, \log n))$ time.},
added-at = {2008-01-03T03:01:58.000+0100},
author = {Batagelj, V. and Zaversnik, M.},
biburl = {https://www.bibsonomy.org/bibtex/204dd5c8a505463b1e196f842b91a8b07/jil},
interhash = {775d7337332536953aaac48aedae1a68},
intrahash = {04dd5c8a505463b1e196f842b91a8b07},
keywords = {core generalized graph kern p reduction subgraph},
note = {cs.DS/0202039},
timestamp = {2013-11-23T20:11:51.000+0100},
title = {Generalized Cores},
url = {http://arxiv.org/ps/cs/0202039},
year = 2002
}