A Linear Time Algorithm for Deciding Interval Graph Isomorphism
From MaRDI portal
Publication:4187325
DOI10.1145/322123.322125zbMath0402.68050OpenAlexW2089081330MaRDI QIDQ4187325
George S. Lueker, Kellogg S. Booth
Publication date: 1979
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://escholarship.org/uc/item/8ss2q7bp
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)
Related Items
Polynomial isomorphism algorithm for graphs which do not pinch to \(K_{3,g}\), Linear-Time Generation of Random Chordal Graphs, Optimal greedy algorithms for indifference graphs, The QAP-polytope and the graph isomorphism problem, Isomorphism of chordal (6, 3) graphs, Computing a dominating pair in an asteroidal triple-free graph in linear time, Graph isomorphism for graph classes characterized by two forbidden induced subgraphs, Solving the canonical representation and star system problems for proper circular-arc graphs in logspace, An efficient parallel algorithm for planarity, Reconstruction of Interval Graphs, Strong tree-cographs are Birkhoff graphs, Intersection graphs of Helly families of subtrees, Reconstruction of interval graphs, A fast parallel algorithm to recognize P4-sparse graphs, Intersection graphs of proper subtrees of unicyclic graphs, Recognizing simple-triangle graphs by restricted 2-chain subgraph cover, On the structure of graphs with few \(P_4\)s, Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable (extended abstract), The Neighborhood Polynomial of Chordal Graphs, Filtering graphs to check isomorphism and extracting mapping by using the conductance electrical model, Parameterized complexity of multicut in weighted trees, Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs, Polynomial time algorithms for variants of graph matching on partial \(k\)-trees, On the isomorphism of graphs having some eigenvalues of moderate multiplicity, Mobility offer allocations in corporate settings, On the isomorphism of graphs with few P4s, Cleaning interval graphs, Random generation and enumeration of bipartite permutation graphs, Coloring mixed and directional interval graphs, A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs, On linear and circular structure of (claw, net)-free graphs, Directed path graph isomorphism, Complement reducible graphs, Induced minor free graphs: isomorphism and clique-width, Integral mixed unit interval graphs, Isomorphism testing of k-trees is in NC, for fixed k, Computing role assignments of proper interval graphs in polynomial time, Subgraph isomorphism in graph classes, An optimal greedy heuristic to color interval graphs, Neighborhood hypergraphs of bipartite graphs, A note on compact graphs, Graph isomorphism and identification matrices: Sequential algorithms, The isomorphism problem for classes of graphs closed under contraction, Computing Role Assignments of Proper Interval Graphs in Polynomial Time, On a unique tree representation for \(P_ 4\)-extendible graphs, A tree representation for \(P_ 4\)-sparse graphs, Tractabilities and intractabilities on geometric intersection graphs, The list distinguishing number equals the distinguishing number for interval graphs, VF2++ -- an improved subgraph isomorphism algorithm, Linear time algorithms for dominating pairs in asteroidal triple-free graphs, A linear-time algorithm for isomorphism of a subclass of chordal graphs, Efficient parallel recognition of some circular arc graphs. I, On the L(h, k)‐labeling of co‐comparability graphs and circular‐arc graphs, Graph theory (algorithmic, algebraic, and metric problems), Random Generation and Enumeration of Proper Interval Graphs, Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs, Simple Geometrical Intersection Graphs, On \(H\)-topological intersection graphs, Graph isomorphism restricted by lists, Canonical representations for circular-arc graphs using flip sets, Recognizing generalized Sierpiński graphs, A selected tour of the theory of identification matrices, On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results, Revising Johnson's table for the 21st century, Graph isomorphism problem, Simulated annealing and the mapping problem: A computational study, Graph recurrence, On the isomorphism problem for Helly circular-arc graphs
