Given a chordal graph $G$, what is the complexity of computing the reduced clique graph $C_r(G)$?
The complexity is O(nm)... from G compute the maximal cliques and make them vertices in your graph H (initially with no edges)... then compute all minimal separators and order them by size... pick the largest separator S and make any two cliques C,C' adjacent in H (connect them by an edge with label S) if C,C' both contain S and are in different connected components of H (initially this is of course always true, but may not be later)... then pick next largest separator and do the same... repeat until all separators are processed... the resulting graph H is the reduced clique graph of G... computing maximal cliques and minimal separators takes O(n+m)... there are O(n) cliques and O(n) separators... the rest of the construction is O(nm) as processing each separator can take O(m) time... 
... this cannot be improved below O(n^2) unless you can solve the following problem: given a graph G find two vertices u,v such that N(u) contains N(v)... the latter is not known to have O(n+m) solution...
... it is therefore unlikely that a O(n+m) algorithm for computing reduced clique graphs is possible...

see Section 5 in M. Habib, J. Stacho: Polynomial-time algorithm for the leafage of chordal graphs, In: Algorithms - ESA 2009, Lecture Notes in Computer Science 5757/2009, pp. 290-300. (http://www.cs.toronto.edu/~stacho/public/leafage-esa1.pdf)