Detecting induced subgraphs

Benjamin Lévêque (), David Y. Lin (), Frédéric Maffray () and Nicolas Trotignon ()
Additional contact information
Benjamin Lévêque: G-SCOP_OC - Optimisation Combinatoire - G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production - UJF - Université Joseph Fourier - Grenoble 1 - Grenoble INP - Institut polytechnique de Grenoble - Grenoble Institute of Technology - INPG - Institut National Polytechnique de Grenoble - CNRS - Centre National de la Recherche Scientifique
David Y. Lin: Princeton University
Frédéric Maffray: G-SCOP_OC - Optimisation Combinatoire - G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production - UJF - Université Joseph Fourier - Grenoble 1 - Grenoble INP - Institut polytechnique de Grenoble - Grenoble Institute of Technology - INPG - Institut National Polytechnique de Grenoble - CNRS - Centre National de la Recherche Scientifique
Nicolas Trotignon: CES - Centre d'économie de la Sorbonne - UP1 - Université Paris 1 Panthéon-Sorbonne - CNRS - Centre National de la Recherche Scientifique

Post-Print from HAL

Abstract: 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 ?".

Keywords: Detection; induced; subgraph; sous-graphe; induit; détection (search for similar items in EconPapers)
Date: 2007-10
Note: View the original document on HAL open archive server: https://shs.hal.science/halshs-00180953v1
References: View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Published in 2007

Downloads: (external link)
https://shs.hal.science/halshs-00180953v1/document (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:halshs-00180953

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().