Detecting induced subgraphs - HAL-SHS - Sciences de l'Homme et de la Société Accéder directement au contenu
Autre Publication Scientifique Documents de travail du Centre d'Économie de la Sorbonne Année : 2007

Detecting induced subgraphs

Benjamin Lévêque
David Y. Lin
  • Fonction : Auteur
  • PersonId : 843668
Frédéric Maffray
Nicolas Trotignon

Résumé

An s-graph is a graph with two kinds of edges : subdivisible edges and real edges. A realisation of an s-graphB is any graph obtained by subdividing subdivisible edges of B into paths of arbitrary length (at least one). Given an s-graph B, we study the decision problem Pi(B) whose instance is a graph G and whose question is "Does G contain a realisation of B as an induced subgraph ?".
Un s-graph est un graphe avec deux sortes d'arêtes : les arêtes subdivisibles et les vraies arêtes. Une réalisation d'un s-graph B est un graphe obtenu en subdivisant des arêtes subdivisibles de B en des chemins de taille arbitraire (au moin un). Etant donné un s-graph B, nous étudions le problème de décision Pi(B) dont l'instance est un graphe G et dont la question est "G contient-il une réalisation de B en tant que sous graphe induit ?".
Fichier principal
Vignette du fichier
B07049.pdf (387.1 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Licence : CC BY - Paternité
Loading...

Dates et versions

halshs-00180953 , version 1 (22-10-2007)

Licence

Paternité

Identifiants

  • HAL Id : halshs-00180953 , version 1

Citer

Benjamin Lévêque, David Y. Lin, Frédéric Maffray, Nicolas Trotignon. Detecting induced subgraphs. 2007. ⟨halshs-00180953⟩
336 Consultations
277 Téléchargements

Partager

Gmail Facebook X LinkedIn More