We continue the study of boundary classes for -hard problems and focus on seven -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 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.

Boundary classes for graph problems involving non-local properties / Munaro, Andrea. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 692:(2017), pp. 46-71. [10.1016/j.tcs.2017.06.012]

Boundary classes for graph problems involving non-local properties

Andrea Munaro
2017-01-01

Abstract

We continue the study of boundary classes for -hard problems and focus on seven -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 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.
2017
Boundary classes for graph problems involving non-local properties / Munaro, Andrea. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 692:(2017), pp. 46-71. [10.1016/j.tcs.2017.06.012]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11381/2937092
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? ND
social impact