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

DOI10.1023/B:ORDE.0000034609.99940.FBzbMATH Open1059.05098OpenAlexW2069161802WikidataQ56430242 ScholiaQ56430242MaRDI QIDQ1771253FDOQ1771253

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

partial orderrecognition algorithmswidthDilworth number

Mathematics Subject Classification ID

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

Cited In (16)

• On pairwise compatibility graphs having Dilworth number \(k\)
• Small Resolution Proofs for QBF using Dependency Treewidth
• Faster Existential FO Model Checking on Posets
• Most balanced minimum cuts
• Isometric Diamond Subgraphs
• Haplotyping with missing data via perfect path phylogenies
• Traversing combinatorial 0/1-polytopes via optimization
• On the complexity of SNP block partitioning under the perfect phylogeny model
• 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 linear-time parameterized algorithm for computing the width of a DAG
• A Path Cover Technique for LCAs in Dags
• Another note on Dilworth's decomposition theorem.
• Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended
• Using decomposition-parameters for QBF: mind the prefix!
• Model checking existential logic on partially ordered sets

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1771253)