Tractabilities and intractabilities on geometric intersection graphs

DOI10.3390/A6010060zbMATH Open1461.05148OpenAlexW1987721329MaRDI QIDQ1736543FDOQ1736543

Authors: Ryuhei Uehara 

Publication date: 26 March 2019

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3390/a6010060

Recommendations

• The complexity of dominating set in geometric intersection graphs
• Approximation Algorithms for Geometric Intersection Graphs
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Contraction-bidimensionality of geometric intersection graphs
• Intersection dimension and graph invariants
• Refining the hierarchies of classes of geometric intersection graphs
• Refining the hierarchies of classes of geometric intersection graphs
• On the structure of certain intersection graphs
• The dominating set problem in geometric intersection graphs
• Geometric intersection patterns and the theory of topological graphs

zbMATH Keywords

bandwidthinterval graphsgraph isomorphismchain graphsthreshold graphsHamiltonian path problemunit grid intersection graphs

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Topics in Intersection Graph Theory
• Graph Classes: A Survey
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Efficient graph representations
• Algorithmic graph theory and perfect graphs
• On computing longest paths in small graph classes
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Simple Geometrical Intersection Graphs
• Title not available (Why is that?)
• Isomorphism of graph classes related to the circular-ones property
• Interval graphs and interval orders
• HAMILTONian circuits in chordal bipartite graphs
• The NP-completeness of the bandwidth minimization problem
• Bandwidth of chain graphs
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• Computing the Bandwidth of Interval Graphs
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
• Title not available (Why is that?)
• Finding Hamiltonian circuits in interval graphs
• A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs
• Exact and approximate bandwidth
• Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
• The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
• Interval bigraphs and circular arc graphs
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• The bandwidth problem for graphs and matrices—a survey
• Title not available (Why is that?)
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Bandwidth of bipartite permutation graphs in polynomial time
• On finding the minimum bandwidth of interval graphs
• Title not available (Why is that?)
• Bandwidth of convex bipartite graphs and related graphs
• Even faster exact bandwidth
• Bandwidth and distortion revisited
• Recognizing interval digraphs and interval bigraphs in polynomial time
• A short proof that `proper = unit'
• Random Generation and Enumeration of Bipartite Permutation Graphs
• On testing isomorphism of permutation graphs
• A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
• Bandwidth of Bipartite Permutation Graphs
• Improved bandwidth approximation for trees and chordal graphs
• Title not available (Why is that?)
• Linear structure of bipartite permutation graphs and the longest path problem
• Bandwidth Minimization: An approximation algorithm for caterpillars
• Finding the minimum bandwidth of an interval graph
• Bandwidth and topological bandwidth of graphs with few \(P_4\)'s
• Algorithms and Computation

Cited In (11)

• On the isomorphism problem for Helly circular-arc graphs
• Intersection-link representations of graphs
• Simple Geometrical Intersection Graphs
• Powers of geometric intersection graphs and dispersion algorithms
• On the intractability landscape of digraph intersection representations
• Can they cross? and how? (the hitchhiker's guide to the universe of geometric intersection graphs)
• Editorial: Special issue on graph algorithms
• Graph isomorphism restricted by lists
• The balanced connected subgraph problem for geometric intersection graphs
• Algorithmic aspects of intersection graphs and representation hypergraphs
• Refining the hierarchies of classes of geometric intersection graphs

This page was built for publication: Tractabilities and intractabilities on geometric intersection graphs

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