A slice theoretic approach for embedding problems on digraphs

DOI10.1007/978-3-662-53174-7_26MaRDI QIDQ2827823zbMATH OpenOpenAlexFDO

Authors 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

directed pathwidthslice languagessubgraph homeomorphismsubgraph isomorphism

Mathematics Subject Classification ID

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

Recommendations

• Embeddings of \(k\)-connected graphs of pathwidth \(k\)
• Characterizations and directed path-width of sequence digraphs
• scientific article; zbMATH DE number 1617252
• Directed path-width of sequence digraphs
• Parameterized algorithms for directed modular width

Cites work

• A Polynomial Time Algorithm for Bounded Directed Pathwidth
• Canonizable partial order generators
• Color-coding
• Digraph complexity measures and applications in formal language theory
• Directed path-width and monotonicity in digraph searching
• Directed tree-width
• Easy problems for tree-decomposable graphs
• Embeddings of \(k\)-connected graphs of pathwidth \(k\)
• Faster algorithms for finding and counting subgraphs
• Finding topological subgraphs is fixed-parameter tractable
• Hasse diagram generators and Petri nets
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• Linear time solvable optimization problems on graphs of bounded clique-width
• On digraph width measures in parameterized algorithmics
• Subgraphs satisfying MSO properties on z-topologically orderable digraphs
• The directed subgraph homeomorphism problem

Cited in

(4)

• A new technique for the link slice problem
• The slice map problem and approximation properties
• The parameterized space complexity of embedding along a path
• Order Reconfiguration under Width Constraints

This page was built for publication: A slice theoretic approach for embedding problems on digraphs

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