The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
DOI10.1137/140963108zbMATH Open1317.05132OpenAlexW2408404065MaRDI QIDQ5499731FDOQ5499731
Publication date: 31 July 2015
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: http://dro.dur.ac.uk/15767/1/15767.pdf
Recommendations
- The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial
- A vertex ordering characterization of simple-triangle graphs
- A recognition algorithm for simple-triangle graphs
- The interval order polytope of a digraph
- Polygonal graphs as ordered sets: the Sperner criterion
- Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
- Linear recognition of almost interval graphs
- The recognition of triangle graphs
- The recognition of triangle graphs
- Recognition of some perfectly orderable graph classes
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62) Combinatorics of partially ordered sets (06A07)
Cites Work
- Graph Classes: A Survey
- Efficient graph representations
- Algorithmic graph theory and perfect graphs
- Threshold graphs and related topics
- Title not available (Why is that?)
- On the Complexity of Timetable and Multicommodity Flow Problems
- The Complexity of the Partial Order Dimension Problem
- Trapezoid graphs and their coloring
- Title not available (Why is that?)
- On the 2-Chain Subgraph Cover and Related Problems
- Title not available (Why is that?)
- Max-tolerance graphs as intersection graphs
- The Recognition of Tolerance and Bounded Tolerance Graphs
- Proper and unit bitolerance orders and graphs
- Triangulating multitolerance graphs
- Linear-Interval Dimension and PI Orders
- The recognition of triangle graphs
- Sufficient Conditions for Graphs to Have Threshold Number 2
- Threshold Numbers and Threshold Completions
- An intersection model for multitolerance graphs: efficient algorithms and hierarchy
Cited In (7)
- Linear-Interval Dimension and PI Orders
- A recognition algorithm for simple-triangle graphs
- A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs
- Forbidden pattern characterizations of 12-representable graphs defined by pattern-avoiding words
- A vertex ordering characterization of simple-triangle graphs
- Recognizing simple-triangle graphs by restricted 2-chain subgraph cover
- The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial
This page was built for publication: The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5499731)
