While converting a tree decomposition of graph to Normalized tree decomposition, the definitions of clique vertex and separator vertex are used in Sequential and parallel algorithms for embedding problems on classes of partial k-trees page: 8-9. Can somebody help me out with the two definitions which are used there.

  • 1
    $\begingroup$ Look at the beginning of Section 3.1, where normalized tree decompositions are defined. When the authors say that the vertices of $T^H$ alternate between separator vertices and clique vertices, I take this to mean that every child of a separator vertex is a clique vertex, and every child of a clique vertex is a separator vertex. I hope this clarifies the situation -- they are intrinsic to the definition of a normalized tree decomposition. $\endgroup$ – Andrew D. King Mar 4 '14 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.