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
David Y. Lin: Princeton University
Frédéric Maffray: G-SCOP
Nicolas Trotignon: Centre d'Economie de la Sorbonne

Documents de travail du Centre d'Economie de la Sorbonne from Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne

Abstract: An s-graph is a graph with two kinds of edges: subdivisible edges and real edges. A realisation of an s-graph B is any graph obtained by 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 (search for similar items in EconPapers)
Pages: 19 pages
Date: 2007-10
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Published in Discrete Applied Mathematics, 157, (17), 2009, pp.3540-3551

Downloads: (external link)
https://shs.hal.science/halshs-00180953 (application/pdf)
https://doi.org/10.1016/j.dam.2009.02.015

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:mse:cesdoc:b07049

Access Statistics for this paper

More papers in Documents de travail du Centre d'Economie de la Sorbonne from Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne Contact information at EDIRC.
Bibliographic data for series maintained by Lucie Label ().