Bruno Escoffier, Laurent Gourvès och Jérôme Monnot. Komplexitet och approximation resultat för den anslutna vertex täcka problem i grafer och hypergrafer. 2007. hal-00178912 Vi studerar en variation av vertex cover problem där det krävs att grafen induceras av vertex cover är ansluten. Vi bevisar att detta problem är polynom i ackordsgrafer, har en PTAS i plana grafer, är APX-hård i bipartit grafer och är 5/3-uppskattbar i alla klasser av grafer där vertex cover problem är polynom (särskilt i bipartit grafer). Slutligen, som handlar om hypergrafer, studerar vi komplexiteten och approximabiliteten av två naturliga generaliseringar.
Escoffier, Gourvès, och Monnot REF förbättrade det senare resultatet genom att visa att Connected Vertex Cover är polynom-tid solvable för ackordsgrafer.
Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
{'venue': 'J. Discrete Algorithms', 'journal': 'J. Discrete Algorithms', 'mag_field_of_study': ['Mathematics', 'Computer Science']}