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

Bomhoff, Matthijs and Kern, Walter and Still, Georg (2012) On bounded block decomposition problems for under-specified systems of equations. Journal of Computer and System Sciences, 78 (1). pp. 336-347. ISSN 0022-0000

PDF
Restricted to UT campus only: Request a copy
311Kb

Abstract:	When solving a system of equations, it can be beneficial not to solve it in its entirety at once, but rather to decompose it into smaller subsystems that can be solved in order. Based on a bisimplicial graph representation we analyze the parameterized complexity of two problems central to such a decomposition: The Free Square Block problem related to finding smallest subsystems that can be solved separately, and the Bounded Block Decomposition problem related to determining a decomposition where the largest subsystem is as small as possible. We show both problems to be W[1]-hard. Finally we relate these problems to crown structures and settle two open questions regarding them using our results.
Item Type:	Article
Copyright:	© 2012 Elsevier
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/79142
Official URL:	http://dx.doi.org/10.1016/j.jcss.2011.05.011
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page