Michel Habib ; Christophe Paul ; Laurent Viennot - Linear time recognition of P4-indifference graphs

dmtcs:269 - Discrete Mathematics & Theoretical Computer Science, January 1, 2001, Vol. 4 no. 2 - https://doi.org/10.46298/dmtcs.269
Linear time recognition of P4-indifference graphsArticle

Authors: Michel Habib ORCID1; Christophe Paul ORCID2; Laurent Viennot ORCID3

  • 1 Laboratoire d'informatique Algorithmique : Fondements et Applications
  • 2 Algorithmes, Graphes et Combinatoire
  • 3 High performance communication


A graph is a P4-indifference graph if it admits an ordering < on its vertices such that every chordless path with vertices a, b, c, d and edges ab, bc, cd has a

https://doi.org/10.46298/dmtcs.269
Source: HAL:inria-00471619v1
Volume: Vol. 4 no. 2
Published on: January 1, 2001
Imported on: March 26, 2015
Keywords: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-WB]Computer Science [cs]/Web

Share and export

Consultation statistics

This page has been seen 537 times.
This article's PDF has been downloaded 411 times.