An intersection model for multitolerance graphs: efficient algorithms and hierarchy
From MaRDI portal
Publication:2249739
DOI10.1007/s00453-012-9743-2zbMath1291.05201OpenAlexW3135965400MaRDI QIDQ2249739
Publication date: 3 July 2014
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: http://dro.dur.ac.uk/13450/1/13450.pdf
Applications of graph theory (05C90) Planar graphs; geometric and topological aspects of graph theory (05C10) Protein sequences, DNA sequences (92D20) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)
Related Items (3)
A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs ⋮ New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs ⋮ The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding the upper envelope of n line segments in O(n log n) time
- Trapezoid graphs and generalizations, geometry and algorithms
- Tolerance graphs
- Proper and unit bitolerance orders and graphs
- Triangulating multitolerance graphs
- Algorithmic graph theory and perfect graphs
- Algorithms for weakly triangulated graphs
- Proper and unit tolerance graphs
- Vertex splitting and the recognition of trapezoid graphs
- A characterization of triangle-free tolerance graphs
- A New Intersection Model and Improved Algorithms for Tolerance Graphs
- The Recognition of Tolerance and Bounded Tolerance Graphs
- Max-tolerance graphs as intersection graphs
- Topics in Intersection Graph Theory
- Tolerance graphs, and orders
- On the 2-Chain Subgraph Cover and Related Problems
This page was built for publication: An intersection model for multitolerance graphs: efficient algorithms and hierarchy
