Directed path graph isomorphism

DOI10.1007/3-540-59071-4_64MaRDI QIDQ6184386zbMATH OpenOpenAlexFDO

Authors Luitpold Babel, Ilya Ponomarenko, Gottfried Tinhofer

Publication date 5 January 2024

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-59071-4_64

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Recommendations

• The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
• Counting maximal independent sets in directed path graphs
• Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
• On the isomorphism of graphs with few P4s
• The isomorphism problem for classes of graphs closed under contraction

Cites work

• scientific article; zbMATH DE number 3545706 (Why is no real title available?)
• scientific article; zbMATH DE number 3558962 (Why is no real title available?)
• scientific article; zbMATH DE number 3575612 (Why is no real title available?)
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• A note on certain subpolytopes of the assignment polytope associated with circulant graphs
• A note on compact graphs
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• A tree representation for \(P_ 4\)-sparse graphs
• Algorithmic graph theory and perfect graphs
• Complement reducible graphs
• Graph isomorphism and theorems of Birkhoff type
• Intersection graphs of paths in a tree
• Isomorphism Testing in Hookup Classes
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• On a unique tree representation for \(P_ 4\)-extendible graphs
• On testing isomorphism of permutation graphs
• Strong tree-cographs are Birkhoff graphs
• The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
• The NP-completeness column: an ongoing guide
• The intersection graphs of subtrees in trees are exactly the chordal graphs

Cited in

(2)

• Isomorphisms and traversability of directed path graphs
• Homomorphisms to oriented paths

This page was built for publication: Directed path graph isomorphism

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