Detecting induced subgraphs

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

MoreLess

Year of publication:	2007-10
Authors:	Lévêque, Benjamin ; Lin, David Y. ; Maffray, Frédéric ; Trotignon, Nicolas
Institutions:	HAL
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:	Post-Print.
Type of publication:	Book / Working Paper
Notes:	View the original document on HAL open archive server: http://halshs.archives-ouvertes.fr/halshs-00180953
Source:	RePEc - Research Papers in Economics

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