Efficient isomorphism for S_d-graphs and T-graphs

DOI10.1007/S00453-022-01033-8MaRDI QIDQ2684481zbMATH OpenOpenAlexFDO

Authors Deniz Ağaoğlu Çağırıcı, Petr Hliněný

Publication date 16 February 2023

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.01495

zbMATH Keywords

\(H\)-graphchordal graphintersection graphisomorphism testingparameterized complexity

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On \(H\)-topological intersection graphs
• scientific article; zbMATH DE number 3815
• Combinatorial problems on \(H\)-graphs
• An improved isomorphism test for bounded-tree-width graphs
• On \(H\)-topological intersection graphs

Cites work

• Algorithmic Aspects of Vertex Elimination on Graphs
• Combinatorial problems on \(H\)-graphs
• Extending partial representations of subclasses of chordal graphs
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
• Graph isomorphism in quasipolynomial time (extended abstract)
• Graph isomorphism problem
• scientific article; zbMATH DE number 3722702 (Why is no real title available?)
• scientific article; zbMATH DE number 49151 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 7740927 (Why is no real title available?)
• Isomorphism of coloured graphs with slowly increasing multiplicity of Jordan blocks
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Isomorphism testing for \(T\)-graphs in FPT
• On \(H\)-topological intersection graphs
• On testing isomorphism of permutation graphs
• On the Cutwidth and the Topological Bandwidth of a Tree
• On the tractability of optimization problems on \(H\)-graphs
• On tractable parameterizations of graph isomorphism
• Precoloring extension. I: Interval graphs
• Recognizing Proper Tree-Graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Topics in Intersection Graph Theory

Cited in

(6)

• scientific article; zbMATH DE number 7559375 (Why is no real title available?)
• Succinct Encodings of Graph Isomorphism
• On \(H\)-topological intersection graphs
• On \(H\)-topological intersection graphs
• Recognition and isomorphism of proper \(H \)-graphs for unicyclic \(H\) in \textit{FPT}-time
• Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable

This page was built for publication: Efficient isomorphism for \(S_d\)-graphs and \(T\)-graphs

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