Detecting induced subgraphs.

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

MoreLess

Year of publication:	2007-10
Authors:	Lévêque, Benjamin ; Lin, David Y. ; Maffray, Frédéric ; Trotignon, Nicolas
Institutions:	Centre d'Économie de la Sorbonne, Université Paris 1 (Panthéon-Sorbonne)
Subject:	Detection \| induced \| subgraph

freely available

Full text |

More access options

Check Google Scholar

In German libraries (KVK)

I need help

More details

Extent:	application/pdf
Series:	Documents de travail du Centre d'Economie de la Sorbonne. - ISSN 1955-611X.
Type of publication:	Book / Working Paper
Notes:	19 pages
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10005510609