scientific article; zbMATH DE number 2192124
From MaRDI portal
Publication:5463498
zbMath1075.05066MaRDI QIDQ5463498
Kathie Cameron, R. Boliac, Vadim V. Lozin
Publication date: 4 August 2005
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (38)
Augmenting approach for some maximum set problems ⋮ Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree ⋮ An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs ⋮ Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ New Results on Directed Edge Dominating Set ⋮ A \(5k\)-vertex kernel for 3-path vertex cover ⋮ A bound on the dissociation number ⋮ The maximum number of maximum dissociation sets in trees ⋮ Relating the independence number and the dissociation number ⋮ On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number ⋮ Extremal vertex-degree function index with given order and dissociation number ⋮ On spectral extrema of graphs with given order and dissociation number ⋮ Uniformly dissociated graphs ⋮ On computing the minimum 3-path vertex cover and dissociation number of graphs ⋮ On the vertex \(k\)-path cover ⋮ Kernelization and Parameterized Algorithms for 3-Path Vertex Cover ⋮ A generalization of Nemhauser and Trotter's local optimization theorem ⋮ 3D-interval-filament graphs ⋮ NP-hard graph problems and boundary classes of graphs ⋮ Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems ⋮ Approximation algorithm for minimum connected 3-path vertex cover ⋮ Improved approximation algorithms for path vertex covers in regular graphs ⋮ Hitting subgraphs in \(P_4\)-tidy graphs ⋮ Minimum \(k\)-path vertex cover ⋮ The complexity of dissociation set problems in graphs ⋮ On a relation between \(k\)-path partition and \(k\)-path vertex cover ⋮ Relating dissociation, independence, and matchings ⋮ The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs ⋮ General d-position sets ⋮ Independent packings in structured graphs ⋮ 3-path vertex cover and dissociation number of hexagonal graphs ⋮ The \(k\)-path vertex cover of rooted product graphs ⋮ The \(k\)-separator problem: polyhedra, complexity and approximation results
This page was built for publication:
