Tractabilities and intractabilities on geometric intersection graphs
From MaRDI portal
Publication:1736543
DOI10.3390/a6010060zbMath1461.05148OpenAlexW1987721329MaRDI QIDQ1736543
Publication date: 26 March 2019
Published in: Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.3390/a6010060
bandwidthchain graphsinterval graphsgraph isomorphismthreshold graphsHamiltonian path problemunit grid intersection graphs
Related Items
The balanced connected subgraph problem for geometric intersection graphs ⋮ Editorial: Special issue on graph algorithms ⋮ Graph isomorphism restricted by lists ⋮ On the isomorphism problem for Helly circular-arc graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Bandwidth of chain graphs
- Bandwidth and distortion revisited
- Exact and approximate bandwidth
- Bandwidth of bipartite permutation graphs in polynomial time
- Interval graphs and interval orders
- Finding Hamiltonian circuits in interval graphs
- Finding the minimum bandwidth of an interval graph
- On finding the minimum bandwidth of interval graphs
- The NP-completeness of the bandwidth minimization problem
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
- A short proof that `proper = unit'
- Recognizing interval digraphs and interval bigraphs in polynomial time
- Efficient graph representations
- Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
- Algorithmic graph theory and perfect graphs
- HAMILTONian circuits in chordal bipartite graphs
- Linear structure of bipartite permutation graphs and the longest path problem
- Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
- Improved Bandwidth Approximation for Trees and Chordal Graphs
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
- ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES
- Bandwidth of Convex Bipartite Graphs and Related Graphs
- Even Faster Exact Bandwidth
- Computing the Bandwidth of Interval Graphs
- Bandwidth of Bipartite Permutation Graphs
- Random Generation and Enumeration of Bipartite Permutation Graphs
- The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
- On testing isomorphism of permutation graphs
- The bandwidth problem for graphs and matrices—a survey
- Bandwidth Minimization: An approximation algorithm for caterpillars
- A Linear Time Algorithm for Deciding Interval Graph Isomorphism
- Topics in Intersection Graph Theory
- Graph Classes: A Survey
- A survey of solved problems and applications on bandwidth, edgesum, and profile of 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
- Approximating the Bandwidth for Asteroidal Triple-Free Graphs
- Interval bigraphs and circular arc graphs
- $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
- Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
- A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
- Simple Geometrical Intersection Graphs
- Algorithms and Computation
- Bandwidth and topological bandwidth of graphs with few \(P_4\)'s
