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

Guardado en:
Detalles Bibliográficos
Autores principales: Lin, M.C., Vasiliev, S.
Formato: JOUR
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: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 todo:paper_00200190_v115_n9_p667_Lin
record_format dspace
spelling todo:paper_00200190_v115_n9_p667_Lin2023-10-03T14:16:40Z Approximation algorithms for clique transversals on some graph classes Lin, M.C. Vasiliev, S. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, M.C.
Vasiliev, S.
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.
format JOUR
author Lin, M.C.
Vasiliev, S.
author_facet Lin, M.C.
Vasiliev, S.
author_sort Lin, M.C.
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
url http://hdl.handle.net/20.500.12110/paper_00200190_v115_n9_p667_Lin
work_keys_str_mv AT linmc approximationalgorithmsforcliquetransversalsonsomegraphclasses
AT vasilievs approximationalgorithmsforcliquetransversalsonsomegraphclasses
_version_ 1782030603831476224

Ejemplares similares