On the computational complexity of (O,P)-partition problems
Jan Kratochvíl; Ingo Schiermeyer
Discussiones Mathematicae Graph Theory (1997)
- Volume: 17, Issue: 2, page 253-258
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topJan Kratochvíl, and Ingo Schiermeyer. "On the computational complexity of (O,P)-partition problems." Discussiones Mathematicae Graph Theory 17.2 (1997): 253-258. <http://eudml.org/doc/270382>.
@article{JanKratochvíl1997,
abstract = {We prove that for any additive hereditary property P > O, it is NP-hard to decide if a given graph G allows a vertex partition V(G) = A∪B such that G[A] ∈ 𝓞 (i.e., A is independent) and G[B] ∈ P.},
author = {Jan Kratochvíl, Ingo Schiermeyer},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {computational complexity; graph properties; partition problems; additive hereditary graph properties},
language = {eng},
number = {2},
pages = {253-258},
title = {On the computational complexity of (O,P)-partition problems},
url = {http://eudml.org/doc/270382},
volume = {17},
year = {1997},
}
TY - JOUR
AU - Jan Kratochvíl
AU - Ingo Schiermeyer
TI - On the computational complexity of (O,P)-partition problems
JO - Discussiones Mathematicae Graph Theory
PY - 1997
VL - 17
IS - 2
SP - 253
EP - 258
AB - We prove that for any additive hereditary property P > O, it is NP-hard to decide if a given graph G allows a vertex partition V(G) = A∪B such that G[A] ∈ 𝓞 (i.e., A is independent) and G[B] ∈ P.
LA - eng
KW - computational complexity; graph properties; partition problems; additive hereditary graph properties
UR - http://eudml.org/doc/270382
ER -
References
top- [1] M.R. Garey and D.S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, New York, 1979. Zbl0411.68039
- [2] J. Bucko, M. Frick, P. Mihok and R. Vasky, Uniquely partitionable graphs, Discussiones Mathematicae Graph Theory 17 (1997) 103-113. Zbl0906.05057
- [3] P. Mihók, G. Semanišin, Additive hereditary properties are uniquely factorizable, Czecho-Slovak Conference on Combinatorics and Graph Theory, Chudenice, 1997.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.