Order Reconfiguration under Width Constraints

DOI10.7155/JGAA.00628MaRDI QIDQ6075707zbMATH OpenOpenAlexFDO

Authors Henning Fernau, Mateus de Oliveira Oliveira, Petra Wolf

Publication date 20 September 2023

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.7155/jgaa.00628

zbMATH Keywords

graph isomorphism problemorder reconfiguration problem

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Reconfiguration in bounded bandwidth and tree-depth
• Impossibility of Transformation of Vertex Labeled Simple Graphs Preserving the Cut-Size Order
• The list coloring reconfiguration problem for bounded pathwidth graphs
• Introduction to reconfiguration
• Reconfiguration of Steiner trees in an unweighted graph

Cites work

• A slice theoretic approach for embedding problems on digraphs
• Abstract completion, formalized
• An improved isomorphism test for bounded-tree-width graphs
• An optimal lower bound on the number of variables for graph identification
• Colored hypergraph isomorphism is fixed parameter tractable
• Cutwidth: obstructions and algorithmic aspects
• Derivation of algorithms for cutwidth and related graph layout parameters
• Fixed-point definability and polynomial time on graphs with excluded minors
• Formalizing Knuth-Bendix orders and Knuth-Bendix completion
• Fundamentals of parameterized complexity
• Graph isomorphism in quasipolynomial time (extended abstract)
• Hasse diagram generators and Petri nets
• scientific article; zbMATH DE number 789389 (Why is no real title available?)
• Introduction to reconfiguration
• Isomorphism for graphs of bounded feedback vertex set number
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Obstruction set isolation for the gate matrix layout problem
• On the complexity of reconfiguration problems
• On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
• Order Reconfiguration Under Width Constraints.
• Recent advances on the graph isomorphism problem
• Reconfiguration in bounded bandwidth and tree-depth
• Searching and pebbling
• Slothrop: Knuth-Bendix Completion with a Modern Termination Checker
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• Subgraphs satisfying MSO properties on z-topologically orderable digraphs
• Term Rewriting and All That
• The Knuth-Bendix Completion Procedure and Thue Systems
• The vertex separation and search number of a graph
• The vertex separation number of a graph equals its path-width

Cited in

(1)

• Order Reconfiguration Under Width Constraints.

This page was built for publication: Order Reconfiguration under Width Constraints

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