### Browsing by Author "Kangas, Kustaa"

Now showing 1 - 3 of 3

###### Results Per Page

###### Sort Options

Item A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions(Springer New York, 2020-08-01) Kangas, Kustaa; Koivisto, Mikko; Salonen, Sami; Department of Computer Science; University of HelsinkiWe investigate the problem of computing the number of linear extensions of a given n-element poset whose cover graph has treewidth t. We present an algorithm that runs in time O~ (nt + 3) for any constant t; the notation O~ hides polylogarithmic factors. Our algorithm applies dynamic programming along a tree decomposition of the cover graph; the join nodes of the tree decomposition are handled by fast multiplication of multivariate polynomials. We also investigate the algorithm from a practical point of view. We observe that the running time is not well characterized by the parameters n and t alone: fixing these parameters leaves large variance in running times due to uncontrolled features of the selected optimal-width tree decomposition. We compare two approaches to select an efficient tree decomposition: one is to include additional features of the tree decomposition to build a more accurate, heuristic cost function; the other approach is to fit a statistical regression model to collected running time data.Both approaches are shown to yield a tree decomposition that typically is significantly more efficient than a random optimal-width tree decomposition.Item On the Number of Connected Sets in Bounded Degree Graphs(Electronic Journal of Combinatorics, 2018) Kangas, Kustaa; Kaski, Petteri; Korhonen, Janne H.; Koivisto, Mikko; Aalto University; Department of Computer Science; University of Helsinki; Department of Computer ScienceA set of vertices in a graph is connected if it induces a connected subgraph. Using Shearer's entropy lemma and a computer search, we show that the number of connected sets in a graph with n vertices and maximum vertex degree d is at most O(1.9351n) for d=3, O(1.9812n) for d=4, and O(1.9940n) for d=5. Dually, we construct infinite families of graphs where the number of connected sets is at least Ω(1.7651n) for d=3, Ω(1.8925n) for d=4, and Ω(1.9375n) for d=5.Item On the number of connected sets in bounded degree graphs(Electronic Journal of Combinatorics, 2018-01-01) Kangas, Kustaa; Kaski, Petteri; Korhonen, Janne H.; Koivisto, Mikko; Department of Computer Science; University of HelsinkiA set of vertices in a graph is connected if it induces a connected subgraph. Using Shearer’s entropy lemma and a computer search, we show that the number of connected sets in a graph with n vertices and maximum vertex degree d is at most O(1.9351 n ) for d = 3, O(1.9812 n ) for d = 4, and O(1.9940 n ) for d = 5. Dually, we construct infinite families of graphs where the number of connected sets is at least Ω(1.7651 n ) for d = 3, Ω(1.8925 n ) for d = 4, and Ω(1.9375 n ) for d = 5.