Search

Your search keyword '"Paul, Christophe"' showing total 20 results
Start Over Author "Paul, Christophe" Publisher springer science and business media llc
20 results on '"Paul, Christophe"'

2. Typical Sequences Revisited — Computing Width Parameters of Graphs

Author

Bodlaender, Hans L., Jaffke, Lars, Telle, Jan Arne, Paul, Christophe, Bläser, Markus, Sub Algorithms and Complexity, and Algorithms and Complexity

Subjects
FOS: Computer and information sciences, typical sequences, 0102 computer and information sciences, 02 engineering and technology, Computer Science::Computational Complexity, Series and parallel circuits, 01 natural sciences, Constructive, Bottleneck, Theoretical Computer Science, Pathwidth, Computer Science::Discrete Mathematics, Computer Science - Data Structures and Algorithms, FOS: Mathematics, treewidth, 0202 electrical engineering, electronic engineering, information engineering, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), series parallel digraphs, Computer Science::Data Structures and Algorithms, Time complexity, Mathematics, Discrete mathematics, Lemma (mathematics), cutwidth, modified cutwidth, 020206 networking & telecommunications, Treewidth, Computational Theory and Mathematics, 010201 computation theory & mathematics, Theory of computation, Combinatorics (math.CO)
Abstract

In this work, we give a structural lemma on merges of typical sequences, a notion that was introduced in 1991 [Lagergren and Arnborg, Bodlaender and Kloks, both ICALP 1991] to obtain constructive linear time parameterized algorithms for treewidth and pathwidth. The lemma addresses a runtime bottleneck in those algorithms but so far it does not lead to asymptotically faster algorithms. However, we apply the lemma to show that the cutwidth and the modified cutwidth of series parallel digraphs can be computed in $\mathcal{O}(n^2)$ time., Comment: 30 pages, 10 figures; accepted at STACS 2020

Published
2021

3. Widespread bacterial diversity within the bacteriome of fungi

Author

Robinson, Aaron J., primary, House, Geoffrey L., additional, Morales, Demosthenes P., additional, Kelliher, Julia M., additional, Gallegos-Graves, La Verne, additional, LeBrun, Erick S., additional, Davenport, Karen W., additional, Palmieri, Fabio, additional, Lohberger, Andrea, additional, Bregnard, Danaé, additional, Estoppey, Aislinn, additional, Buffi, Matteo, additional, Paul, Christophe, additional, Junier, Thomas, additional, Hervé, Vincent, additional, Cailleau, Guillaume, additional, Lupini, Simone, additional, Nguyen, Hang N., additional, Zheng, Amy O., additional, Gimenes, Luciana Jandelli, additional, Bindschedller, Saskia, additional, Rodrigues, Debora F., additional, Werner, James H., additional, Young, Jamey D., additional, Junier, Pilar, additional, and Chain, Patrick S. G., additional

Published
2021
Full Text
View/download PDF

20. A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions

Author

Sami Salonen, Mikko Koivisto, Kustaa Kangas, Paul, Christophe, Pilipczuk, Michal, Doctoral Programme in Computer Science, Department of Computer Science, University Management, University of Helsinki, Aalto-yliopisto, and Aalto University

Subjects
Multivariate polynomial, General Computer Science, 0102 computer and information sciences, 02 engineering and technology, Running time, Trees (mathematics), 01 natural sciences, Tilde, Algorithm selection, Cover graph, Linear extensions, Linear extension, 111 Mathematics, Parameter estimation, 0202 electrical engineering, electronic engineering, information engineering, Empirical hardness, Multiplication of polynomials, Exclusion algorithms, Mathematics, COMPLEXITY, 000 Computer science, knowledge, general works, Counting linear extensions, Estimation theory, Applied Mathematics, Tree decomposition, FRAMEWORK, 113 Computer and information sciences, Fast multiplication, Computer Science Applications, Dynamic programming, Treewidth, 010201 computation theory & mathematics, Computer Science, Theory of computation, 020201 artificial intelligence & image processing, Partially ordered set, Algorithm
Abstract

We investigate the problem of computing the number of linear extensions of a givenn-element poset whose cover graph has treewidtht. We present an algorithm that runs in time$${\tilde{O}}(n^{t+3})$$O~(nt+3)for any constantt; the notation$${\tilde{O}}$$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 parametersnandtalone: 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.

Published
2019

Catalog

Books, media, physical & digital resources
See catalog results