An intersection model for multitolerance graphs: efficient algorithms and hierarchy

DOI10.1007/S00453-012-9743-2MaRDI QIDQ2249739zbMATH OpenOpenAlexFDO

Authors George B. Mertzios

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

zbMATH Keywords

intersection modelmaximum cliquemaximum weightminimum coloringmultitolerance graphstolerance graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Signed and weighted graphs (05C22) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Applications of graph theory (05C90) Protein sequences, DNA sequences (92D20)

Recommendations

• An intersection model for multitolerance graphs: efficient algorithms and hierarchy
• A new intersection model and improved algorithms for tolerance graphs
• A new intersection model and improved algorithms for tolerance graphs
• New geometric representations and domination problems on tolerance and multitolerance graphs
• New geometric representations and domination problems on tolerance and multitolerance graphs.

Cites work

• A characterization of triangle-free tolerance graphs
• A new intersection model and improved algorithms for tolerance graphs
• Algorithm design: Foundations, analysis, and Internet examples
• Algorithmic graph theory and perfect graphs
• Algorithms for weakly triangulated graphs
• Finding the upper envelope of n line segments in O(n log n) time
• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 3853140 (Why is no real title available?)
• scientific article; zbMATH DE number 2090048 (Why is no real title available?)
• scientific article; zbMATH DE number 2117210 (Why is no real title available?)
• scientific article; zbMATH DE number 2197877 (Why is no real title available?)
• Max-tolerance graphs as intersection graphs
• On the 2-Chain Subgraph Cover and Related Problems
• Proper and unit bitolerance orders and graphs
• Proper and unit tolerance graphs
• The recognition of tolerance and bounded tolerance graphs
• Tolerance graphs
• Tolerance graphs, and orders
• Topics in Intersection Graph Theory
• Trapezoid graphs and generalizations, geometry and algorithms
• Triangulating multitolerance graphs
• Vertex splitting and the recognition of trapezoid graphs

Cited in

(9)

• New geometric representations and domination problems on tolerance and multitolerance graphs
• A new intersection model and improved algorithms for tolerance graphs
• Max point-tolerance graphs
• A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
• scientific article; zbMATH DE number 867635 (Why is no real title available?)
• On central max-point-tolerance graphs
• An intersection model for multitolerance graphs: efficient algorithms and hierarchy
• The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
• A new intersection model and improved algorithms for tolerance graphs

This page was built for publication: An intersection model for multitolerance graphs: efficient algorithms and hierarchy

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