Recognition algorithms for orders of small width and graphs of small Dilworth number

DOI10.1023/B:ORDE.0000034609.99940.fbzbMath1059.05098OpenAlexW2069161802WikidataQ56430242 ScholiaQ56430242MaRDI QIDQ1771253

Stefan Felsner, Vijay Raghavan, Jeremy P. Spinrad

Publication date: 7 April 2005

Published in: Order (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/b:orde.0000034609.99940.fb

zbMATH Keywords

widthpartial orderrecognition algorithmsDilworth number

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (15)

Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended ⋮ Haplotyping with missing data via perfect path phylogenies ⋮ Small Resolution Proofs for QBF using Dependency Treewidth ⋮ A linear-time parameterized algorithm for computing the width of a DAG ⋮ Graph classes with structured neighborhoods and algorithmic applications ⋮ Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU ⋮ A Path Cover Technique for LCAs in Dags ⋮ Model checking existential logic on partially ordered sets ⋮ Another note on Dilworth's decomposition theorem. ⋮ On pairwise compatibility graphs having Dilworth number \(k\) ⋮ Most balanced minimum cuts ⋮ Isometric Diamond Subgraphs ⋮ Faster Existential FO Model Checking on Posets ⋮ Using decomposition-parameters for QBF: mind the prefix! ⋮ On the complexity of SNP block partitioning under the perfect phylogeny model

This page was built for publication: Recognition algorithms for orders of small width and graphs of small Dilworth number