A Slice Theoretic Approach for Embedding Problems on Digraphs

DOI10.1007/978-3-662-53174-7_26zbMath1417.05129OpenAlexW2494713125MaRDI QIDQ2827823

Mateus de Oliveira Oliveira

Publication date: 21 October 2016

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

Full work available at URL: https://doi.org/10.1007/978-3-662-53174-7_26

zbMATH Keywords

subgraph isomorphismdirected pathwidthsubgraph homeomorphismslice languages

Mathematics Subject Classification ID

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

Related Items (1)

Order Reconfiguration under Width Constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Faster algorithms for finding and counting subgraphs
• The directed subgraph homeomorphism problem
• Embeddings of \(k\)-connected graphs of pathwidth \(k\)
• Directed tree-width
• Linear time solvable optimization problems on graphs of bounded clique-width
• Directed path-width and monotonicity in digraph searching
• Subgraphs Satisfying MSO Properties on z-Topologically Orderable Digraphs
• Canonizable Partial Order Generators
• A Polynomial Time Algorithm for Bounded Directed Pathwidth
• Easy problems for tree-decomposable graphs
• On Digraph Width Measures in Parameterized Algorithmics
• Color-coding
• Finding topological subgraphs is fixed-parameter tractable
• Hasse Diagram Generators and Petri Nets

This page was built for publication: A Slice Theoretic Approach for Embedding Problems on Digraphs