scientific article; zbMATH DE number 108280

MaRDI QIDQ4023737zbMATH OpenFDO

Authors Jens Gustedt

Publication date 23 January 1993

zbMATH Keywords

0-1-law for hereditary propertiesaverage-case complexitybounded decomposition diameterchain minor relationcographsfinite formal languagesfinite graphsinduced subgraph relationinduced suborderparallel machineparallelizationquasi-orderswell-quasi-orderingsworst-case complexity

Mathematics Subject Classification ID

Partial orders, general (06A06) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 475611
• Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications
• Well quasi ordering finite posets and formal languages
• scientific article; zbMATH DE number 3926975
• On the complexity of partial order properties

Cited in

(19)

• Parcours dans les graphes: Un outil pour l'algorithmique des ensembles ordonnés
• The order of Appel's algorithm
• On well quasiordering of finite languages
• Data structures for order-sensitive predicates in parallel nondeterministic systems
• Chain minors are FPT
• Minimal antichains in well-founded quasi-orders with an application to tournaments
• Hermes: a simple and efficient algorithm for building the AOC-poset of a binary relation
• Chain minors are FPT
• A Framework for Order-Sorted Algebra
• Order-Sorted Parameterization and Induction
• The ideal approach to computing closed subsets in well-quasi-orderings
• scientific article; zbMATH DE number 6536488 (Why is no real title available?)
• scientific article; zbMATH DE number 475611 (Why is no real title available?)
• scientific article; zbMATH DE number 1554934 (Why is no real title available?)
• scientific article; zbMATH DE number 1885201 (Why is no real title available?)
• scientific article; zbMATH DE number 2242592 (Why is no real title available?)
• Combinatorics and algorithms for quasi-chain graphs
• Combinatorics and algorithms for quasi-chain graphs
• Order-N methodologies and their applications

This page was built for publication:

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