Layer-based width for \textbf{PAFP} on DAGs: a BFS-width-2 normal form and exact-length width-2 tractability

DOI10.1007/978-3-032-27732-9_22MaRDI QIDQ7363392zbMATH OpenFDO

Authors Samuel German

Publication date 29 September 2026

Full work available at URL https://doi.org/10.1007/978-3-032-27732-9_22

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cites work

• Bandwidth vs BFS width in matrix reordering, graph reconstruction, and graph drawing
• Constraint satisfaction with bounded treewidth revisited
• Easy problems for tree-decomposable graphs
• Finding detours is fixed-parameter tractable
• Kernel bounds for path and cycle problems
• Layered separators in minor-closed graph classes with applications
• On paths avoding forbidden pairs of vertices in a graph
• On the complexity of paths avoiding forbidden pairs
• Topological sorting of large networks
• Track layouts, layered path decompositions, and leveled planarity

This page was built for publication: Layer-based width for \textbf{PAFP} on DAGs: a BFS-width-2 normal form and exact-length width-2 tractability

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