On bounded block decomposition problems for under-specified systems of equations

DOI10.1016/j.jcss.2011.05.011zbMath1237.68096MaRDI QIDQ414888

Walter Kern, Georg Still, Matthijs Bomhoff

Publication date: 11 May 2012

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

Full work available at URL: https://research.utwente.nl/en/publications/on-bounded-block-decomposition-problems-for-underspecified-systems-of-equations(2d979d39-7a5d-4662-856a-b70ec62c3796).html

zbMATH Keywords

decomposition; bipartite graphs; parameterized complexity

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Uses Software

• GPDOF

Cites Work

• Unnamed Item
• Unnamed Item
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Matching theory
• Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• Crown structures for vertex cover kernelization
• Crown reductions for the minimum weighted vertex cover problem
• Coverings of Bipartite Graphs
• DECOMPOSITION OF GEOMETRIC CONSTRAINT SYSTEMS: A SURVEY
• Towards a Taxonomy of Techniques for Designing Parameterized Algorithms
• Computing the block triangular form of a sparse matrix
• On Representatives of Subsets
• Graph-Theoretic Concepts in Computer Science
• On the Inversion of Sparse Matrices
• Systems of Distinct Representatives