Induced-path partition on graphs with special blocks
Resource
Theoretical Computer Science 370 (1-3): 121-130
Journal
Theoretical Computer Science
Journal Volume
370
Journal Issue
1-3
Pages
121-130
Date Issued
2007
Author(s)
Abstract
In a graph, an induced path is a path v0, v1, ..., vr in which a vertex vi is adjacent to another vertex vj if and only if | i - j | = 1. An induced-path partition of a graph is a collection of vertex-disjoint induced paths that cover all vertices of the graph. The induced-path-partition problem is to determine the minimum cardinality of an induced-path partition of a graph. This paper presents an O (| V | + | E |)-time algorithm for the induced-path-partition problem on graphs whose blocks are complete graphs, cycles or complete bipartite graphs. © 2006 Elsevier Ltd. All rights reserved.
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
11.pdf
Size
24.16 KB
Format
Adobe PDF
Checksum
(MD5):aae9fbca497dae2d167159cde6bba48f