Boundary classes for graph problems involving non-local properties
2017
Abstract We continue the study of boundary classes for NP -hard problems and focus on seven NP -hard graph problems involving non-local properties: Hamiltonian Cycle , Hamiltonian Cycle Through Specified Edge , Hamiltonian Path , Feedback Vertex Set , Connected Vertex Cover , Connected Dominating Set and Graph VC CON Dimension . Our main result is the determination of the first boundary class for Feedback Vertex Set . We also determine boundary classes for Hamiltonian Cycle Through Specified Edge and Hamiltonian Path and give some insights on the structure of some boundary classes for the remaining problems.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
62
References
23
Citations
NaN
KQI