On the computational complexity of ordered subgraph recognition

DOI10.1002/rsa.3240070304zbMath0834.68052OpenAlexW1979190428MaRDI QIDQ4851929

Dwight Duffus, Vojtěch Rödl, Mark Ginn

Publication date: 5 March 1996

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.3240070304

zbMATH Keywords

computational complexitydecision problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items (4)

Proper and unit bitolerance orders and graphs ⋮ Recognizing interval bigraphs by forbidden patterns ⋮ On grounded \(\llcorner\)-graphs and their relatives ⋮ Graph Classes and Forbidden Patterns on Three Vertices

Cites Work

• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• Topics on perfect graphs
• On the complexity of recognizing perfectly orderable graphs
• Some simplified NP-complete graph problems
• Graphs with linearly bounded Ramsey numbers
• Incidence matrices and interval graphs
• Edge-Disjoint Spanning Trees of Finite Graphs
• Four classes of perfectly orderable graphs
• The Ramsey Property for Families of Graphs Which Exclude a Given Graph
• Total Ordering Problem
• Probability Inequalities for Sums of Bounded Random Variables
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• The NP-completeness column: An ongoing guide

This page was built for publication: On the computational complexity of ordered subgraph recognition