Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms

DOI10.1016/j.jcss.2003.09.003zbMath1091.68076OpenAlexW2037479769MaRDI QIDQ1877711

Jian'er Chen, Iyad A. Kanj

Publication date: 19 August 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2003.09.003

zbMATH Keywords

Vertex coverBipartite graphGraph matchingParameterized computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

On the kernelization of split graph problems, On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs, Constraint Bipartite Vertex Cover Simpler Exact Algorithms and Implementations, On bounded block decomposition problems for under-specified systems of equations, On the partial vertex cover problem in bipartite graphs -- a parameterized perspective, Constraint bipartite vertex cover: simpler exact algorithms and implementations, Observability analysis and sensor location study for structured linear systems in descriptor form with unknown inputs, Multi-Budgeted Directed Cuts, Crown reductions for the minimum weighted vertex cover problem, State and input observability recovering by additional sensor implementation: a graph-theoretic approach, An Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs, Cardinality constrained and multicriteria (multi)cut problems, New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition, Vertex and edge covers with clustering properties: Complexity and algorithms, Multi-budgeted directed cuts, Parameterized computation and complexity: a new approach dealing with NP-hardness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improved fixed-parameter algorithm for vertex cover
• Matching theory
• A general method to speed up fixed-parameter-tractable algorithms
• Solving large FPT problems on coarse-grained parallel machines
• An Efficient Exact Algorithm for Constraint Bipartite Vertex Cover
• Vertex Cover: Further Observations and Further Improvements
• Algorithms for maximum independent sets
• Vertex packings: Structural properties and algorithms
• Generation of minimal vertex covers for row/column allocation in self-repairable arrays
• A new class of efficient algorithms for reconfiguration of memory arrays
• The complexity of type inference for higher-order typed lambda calculi