On computational aspects of ordered matching problems

DOI10.1007/978-3-032-11176-0_27MaRDI QIDQ6840974zbMATH OpenFDO

Authors Michal Čertík, Andreas Emil Feldmann, J. Nešetřil, Paweł Rzążewski

Publication date 20 March 2026

Full work available at URL https://doi.org/10.1007/978-3-032-11176-0_27

zbMATH Keywords

computational complexityhomomorphismsordered coreordered graphsordered matchingsparameterized complexity

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• Chromatic number of ordered graphs with forbidden ordered subgraphs
• Forbidden paths and cycles in ordered graphs and matrices
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 863494 (Why is no real title available?)
• scientific article; zbMATH DE number 3293585 (Why is no real title available?)
• On the computational complexity of ordered subgraph recognition
• Pattern matching for permutations
• Ramsey numbers of ordered graphs
• Twin-width and permutations

This page was built for publication: On computational aspects of ordered matching problems

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