Approximation algorithms for clique transversals on some graph classes

Given a graph G=(V,E) a clique is a maximal subset of pairwise adjacent vertices of V of size at least 2. A clique transversal is a subset of vertices that intersects the vertex set of each clique of G. Finding a minimum-cardinality clique transversal is NP-hard for the following classes: planar, li...

Descripción completa

Detalles Bibliográficos
Autor principal: Lin, Min Chih
Publicado: 2015
Materias:
Approximation algorithms
Clique transversal
Graph classes
NP-hard
Algorithms
Distributed computer systems
Graph theory
Graphic methods
Adjacent vertices
Bounded degree graphs
Cardinalities
Graph class
Non negatives
Planar graph
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v115_n9_p667_Lin
http://hdl.handle.net/20.500.12110/paper_00200190_v115_n9_p667_Lin
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_00200190_v115_n9_p667_Lin
record_format dspace
spelling paper:paper_00200190_v115_n9_p667_Lin2023-06-08T14:40:21Z Approximation algorithms for clique transversals on some graph classes Lin, Min Chih Approximation algorithms Clique transversal Graph classes NP-hard Algorithms Distributed computer systems Graph theory Graphic methods Adjacent vertices Bounded degree graphs Cardinalities Clique transversal Graph class Non negatives NP-hard Planar graph Approximation algorithms Given a graph G=(V,E) a clique is a maximal subset of pairwise adjacent vertices of V of size at least 2. A clique transversal is a subset of vertices that intersects the vertex set of each clique of G. Finding a minimum-cardinality clique transversal is NP-hard for the following classes: planar, line and bounded degree graphs. For line graphs we present a 3-approximation for the unweighted case and a 4-approximation for the weighted case with nonnegative weights; a ⌈(Δ(G)+1)/2 ⌉(-approximation for bounded degree graphs and a 3-approximation for planar graphs. © 2015 Elsevier B.V. Fil:Lin, M.C. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2015 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v115_n9_p667_Lin http://hdl.handle.net/20.500.12110/paper_00200190_v115_n9_p667_Lin
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Approximation algorithms
Clique transversal
Graph classes
NP-hard
Algorithms
Distributed computer systems
Graph theory
Graphic methods
Adjacent vertices
Bounded degree graphs
Cardinalities
Clique transversal
Graph class
Non negatives
NP-hard
Planar graph
Approximation algorithms
spellingShingle Approximation algorithms
Clique transversal
Graph classes
NP-hard
Algorithms
Distributed computer systems
Graph theory
Graphic methods
Adjacent vertices
Bounded degree graphs
Cardinalities
Clique transversal
Graph class
Non negatives
NP-hard
Planar graph
Approximation algorithms
Lin, Min Chih
Approximation algorithms for clique transversals on some graph classes
topic_facet Approximation algorithms
Clique transversal
Graph classes
NP-hard
Algorithms
Distributed computer systems
Graph theory
Graphic methods
Adjacent vertices
Bounded degree graphs
Cardinalities
Clique transversal
Graph class
Non negatives
NP-hard
Planar graph
Approximation algorithms
description Given a graph G=(V,E) a clique is a maximal subset of pairwise adjacent vertices of V of size at least 2. A clique transversal is a subset of vertices that intersects the vertex set of each clique of G. Finding a minimum-cardinality clique transversal is NP-hard for the following classes: planar, line and bounded degree graphs. For line graphs we present a 3-approximation for the unweighted case and a 4-approximation for the weighted case with nonnegative weights; a ⌈(Δ(G)+1)/2 ⌉(-approximation for bounded degree graphs and a 3-approximation for planar graphs. © 2015 Elsevier B.V.
author Lin, Min Chih
author_facet Lin, Min Chih
author_sort Lin, Min Chih
title Approximation algorithms for clique transversals on some graph classes
title_short Approximation algorithms for clique transversals on some graph classes
title_full Approximation algorithms for clique transversals on some graph classes
title_fullStr Approximation algorithms for clique transversals on some graph classes
title_full_unstemmed Approximation algorithms for clique transversals on some graph classes
title_sort approximation algorithms for clique transversals on some graph classes
publishDate 2015
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v115_n9_p667_Lin
http://hdl.handle.net/20.500.12110/paper_00200190_v115_n9_p667_Lin
work_keys_str_mv AT linminchih approximationalgorithmsforcliquetransversalsonsomegraphclasses
_version_ 1768545630561501184

Ejemplares similares