Browsing Computer Science by Subject "parameterized complexity"
Now showing items 1-3 of 3
-
Characterizing Hardness in Parameterized Complexity
(University of Waterloo, 2007-05-18)Parameterized complexity theory relaxes the classical notion of tractability and allows to solve some classically hard problems in a reasonably efficient way. However, many problems of interest remain intractable in the ... -
A Parameterized Algorithm for Upward Planarity Testing of Biconnected Graphs
(University of Waterloo, 2003)We can visualize a graph by producing a geometric representation of the graph in which each node is represented by a single point on the plane, and each edge is represented by a curve that connects its two ... -
Representations and Parameterizations of Combinatorial Auctions
(University of Waterloo, 2007-12-20)Combinatorial auctions (CAs) are an important mechanism for allocating multiple items while allowing agents to specify preferences over bundles of items. In order to communicate these preferences, agents submit bids, which ...