A linear-time parameterized algorithm for computing the width of a DAG
From MaRDI portal
Publication:2672441
DOI10.1007/978-3-030-86838-3_20OpenAlexW3174949429MaRDI QIDQ2672441
Brendan Mumey, Manuel O. Cáceres, Alexandru I. Tomescu, Massimo Cairo, Romeo Rizzi
Publication date: 8 June 2022
Full work available at URL: https://arxiv.org/abs/2007.07575
Cites Work
- Unnamed Item
- Minimizing setups in ordered sets of fixed width
- On-line chain partitions of orders: a survey
- Haplotyping with missing data via perfect path phylogenies
- Edge-disjoint spanning trees and depth-first search
- Recognition algorithms for orders of small width and graphs of small Dilworth number
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- A linear-time algorithm for the perfect phylogeny haplotype problem
- A decomposition theorem for partially ordered sets
- Introduction to Combinatorics
- Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width
- Note on Dilworth's Decomposition Theorem for Partially Ordered Sets
- Topological sorting of large networks
- Nonlinear dynamic analysis of the viscoelastic string with a harmonically varying transport speed
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
- Model checking existential logic on partially ordered sets
- Sparse Dynamic Programming on DAGs with Small Width
- Data Reduction for Maximum Matching on Real-World Graphs
- Max flows in O(nm) time, or better
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
