Approximating Bounded Degree Deletion via Matroid Matching (Q5283370)

scientific article; zbMATH DE number 6751065

Language	Label	Description	Also known as
English	Approximating Bounded Degree Deletion via Matroid Matching	scientific article; zbMATH DE number 6751065

Statements

instance of

scholarly article

0 references

title

Approximating Bounded Degree Deletion via Matroid Matching (English)

0 references

author

Toshihiro Fujito

0 references

published in

Lecture Notes in Computer Science

0 references

publication date

21 July 2017

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1007/978-3-319-57586-5_20

0 references

cites work

Clique Relaxations in Social Network Analysis: The Maximum <i>k</i>-Plex Problem

0 references

On bounded-degree vertex deletion parameterized by treewidth

0 references

On the vertex \(k\)-path cover

0 references

Minimum \(k\)-path vertex cover

0 references

On the weighted \(k\)-path vertex cover problem

0 references

Random pseudo-polynomial algorithms for exact matroid problems

0 references

A Linear Kernel for Co-Path/Cycle Packing

0 references

Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs

0 references

On the hardness of approximating minimum vertex cover

0 references

A generalization of Nemhauser and Trotter's local optimization theorem

0 references

Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems

0 references

A unified approximation algorithm for node-deletion problems

0 references

Approximating Node-Deletion Problems for Matroidal Properties

0 references

On approximation of the submodular set cover problem

0 references

On the \(k\)-path vertex cover of some graph products

0 references

Q4119222

0 references

A better approximation ratio for the vertex cover problem

0 references

On computing the minimum 3-path vertex cover and dissociation number of graphs

0 references

Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

0 references

Matroid Matching: The Power of Local Search

0 references

The node-deletion problem for hereditary properties is NP-complete

0 references

Matroid matching and some applications

0 references

Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes

0 references

Randomized Parallel Algorithms for Matroid Union and Intersection, with Applications to Arborescences and Edge-Disjoint Spanning Trees

0 references

Every Property of Hyperfinite Graphs Is Testable

0 references

A new approach for approximating node deletion problems

0 references

The complexity of dissociation set problems in graphs

0 references

A graph‐theoretic generalization of the clique concept

0 references

A fixed-parameter algorithm for the vertex cover \(P_3\) problem

0 references

The vertex cover \(P_3\) problem in cubic graphs

0 references

A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem

0 references

A primal-dual approximation algorithm for the vertex cover \(P^3\) problem

0 references

An analysis of the greedy algorithm for the submodular set covering problem

0 references

On a generalization of Nemhauser and Trotter's local optimization theorem

0 references

Node-Deletion Problems on Bipartite Graphs

0 references

Identifiers

zbMATH Open document ID

1486.68130

0 references

DOI

10.1007/978-3-319-57586-5_20

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5283370