UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Fast counting of medium-sized rooted subgraphs

Maugis, P-AG; Olhede, SC; Wolfe, PJ; Fast counting of medium-sized rooted subgraphs.

Full text not available from this repository.

Abstract

We prove that counting copies of any graph $F$ in another graph $G$ can be achieved using basic matrix operations on the adjacency matrix of $G$. Moreover, the resulting algorithm is competitive for medium-sized $F$: our algorithm recovers the best known complexity for rooted 6-clique counting and improves on the best known for 9-cycle counting. Underpinning our proofs is the new result that, for a general class of graph operators, matrix operations are homomorphisms for operations on rooted graphs.

Type: Article
Title: Fast counting of medium-sized rooted subgraphs
Additional information: 29 pages, 6 figures
Keywords: cs.DM, cs.DM, cs.SI, math.CO, 68Q25, 90C35, 68R10, 05C50
UCL classification: UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Statistical Science
URI: http://discovery.ucl.ac.uk/id/eprint/1538112
Downloads since deposit
0Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item