New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs

DOI10.1137/15M1039468zbMath1344.05100OpenAlexW2963060183MaRDI QIDQ2820855

Archontia C. Giannopoulou, George B. Mertzios

Publication date: 9 September 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/15m1039468

zbMATH Keywords

polynomial-time algorithmgeometric representationdominating set problemAPX-hardnesstolerance graphmultitolerance graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (3)

A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs ⋮ Paired-domination problem on distance-hereditary graphs ⋮ Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• Tolerance graphs
• Triangulating multitolerance graphs
• Efficient graph representations
• Proper and unit tolerance graphs
• HAMILTONian circuits in chordal bipartite graphs
• An intersection model for multitolerance graphs: efficient algorithms and hierarchy
• A characterization of triangle-free tolerance graphs
• The Design of Approximation Algorithms
• A New Intersection Model and Improved Algorithms for Tolerance Graphs
• The Recognition of Tolerance and Bounded Tolerance Graphs
• Domination on Cocomparability Graphs
• Max-tolerance graphs as intersection graphs
• Dominating Sets in Chordal Graphs
• Tolerance graphs, and orders
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs

This page was built for publication: New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs