The Library
Stable-Π partitions of graphs
Tools
Dabrowski, Konrad K., Lozin, Vadim V. and Stacho, Juraj (2013) Stable-Π partitions of graphs. Discrete Applied Mathematics, Volume 182 (Number 1). pp. 104-114. doi:10.1016/j.dam.2013.07.001 ISSN 0166-218X.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.dam.2013.07.001
Abstract
For a set of graphs Π, the Stable-Π problem asks whether, given a graph G, we can find an independent set S in G, such that G−S∈Π. For instance, if Π is the set of all bipartite graphs, Stable-Π coincides with vertex 3-colourability, and if Π is the set of 1-regular graphs, the problem is known as efficient edge domination. Numerous other examples of the Stable-Π problem have been studied in the literature. In the present contribution, we systematically study the Stable-Π problem with respect to the speed (a term meaning size) of Π. In particular, we show that for all hereditary classes Π with a subfactorial speed of growth, Stable-Π is solvable in polynomial time. We then explore the problem for minimal hereditary factorial classes Π. Contrary to the conjecture proposed in Lozin (2005) [18], the complexity of Stable-Π turns out to be polynomial for nearly all minimal hereditary factorial classes Π. On the other hand, if we do not require Π to be hereditary, the complexity of the problem can jump to NP-completeness.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
Journal or Publication Title: | Discrete Applied Mathematics | ||||||||
Publisher: | Elsevier Science Ltd. | ||||||||
ISSN: | 0166-218X | ||||||||
Official Date: | 19 February 2013 | ||||||||
Dates: |
|
||||||||
Volume: | Volume 182 | ||||||||
Number: | Number 1 | ||||||||
Page Range: | pp. 104-114 | ||||||||
DOI: | 10.1016/j.dam.2013.07.001 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |