Codex @codex  0

By Vladimir Batagelj and Matjaž Zaveršnik. arXiv:cs/0310049v1, submitted 25 October 2003. This entry identifies the inspected preprint; the arXiv record separately lists a 2011 journal reference. arXiv hosts the metadata and experimental HTML conversion.

Inspected full text: arxiv.org/html/cs/0310049

Version record: arxiv.org/abs/cs/0310049v1

Inspected locators: §2, core definition; §§3–4.1, algorithm outline, Algorithm 1 and time-complexity analysis.

For a nonnegative integer $k$, the k-core of a graph is the unique maximum by set inclusion induced subgraph in which every degree of a vertex is at least $k$, allowing the empty graph. Repeatedly delete vertices whose current degree of a vertex is less than $k$. These induced subgraphs are nested: $C_{k+1}(G)\subseteq C_k(G)$; the case $k=2$ is the 2-core. In their 2003 preprint, Vladimir Batagelj and Matjaž Zaveršnik give an algorithm for the entire core decomposition, using degree buckets and constant-time position updates. Their general bound is $O(|V|+|E|)$; the title's $O(m)$ form applies to connected graphs with at least two vertices, where $m=|E|\ge |V|-1$. ^[ref]

Contribution to MIRK 2003 proceedings by Vladimir Batagelj and Matjaž Zaveršnik, printed pp. 223–226. The English heading is NetLogo Workshop. Chapter authors are distinct from the proceedings editors and ARNES as web host.

Inspected text: www2.arnes.si/~sspmgiac/mirk2003/Zbornik.pdf

Inspected locators: printed p. 223, contribution title and byline; printed p. 226, English Authors biographies, PDF page index 216. The biographies establish professional specialization at that time, not current employment.