A Simple Paradigm for Graph Recognition: Application to Cographs and Distance Hereditary Graphs

Damiand G., Habib M., Paul C.

Theoretical Computer Science (TCS)
Volume 263, Number 1-2, pages 99-111, July 2001

Abstract: An easy way for graphs recognition algorithms is to use a two-steps process. First compute a characteristic feature as if the graph belong to that class. Secondly check whether the computed feature really defines the input graphs. Although in some cases the two steps can be merged. But separating them may yield to new and much more easily understood algorithms. In this paper we apply that paradigm to the cographs and distance hereditary graphs recognition problem.

Keywords: Classes of graphs; Recognition algorithms; Cographs; Distance hereditary graphs

BibTex references

@Article{DamiandAl01,
      author = {Damiand, G. and Habib, M. and Paul, C.},
      title = {A Simple Paradigm for Graph Recognition: Application to Cographs and Distance Hereditary Graphs},
      journal = {Theoretical Computer Science (TCS)},
      publisher = {Elsevier},
      volume = {263},
      number = {1-2},
      pages = {99-111},
      month = {July},
      year = {2001},
      keywords = {Classes of graphs; Recognition algorithms; Cographs; Distance hereditary graphs},
      url = {https://dx.doi.org/10.1016/S0304-3975(00)00234-6}
}

Guillaume Damiand

A Simple Paradigm for Graph Recognition: Application to Cographs and Distance Hereditary Graphs

Links:

BibTex references

Image