Faster graph algorithms through DAG compression

DOI10.4230/LIPICS.STACS.2024.8MaRDI QIDQ6902718zbMATH OpenFDO

Authors Max Bannach, Florian Andreas Marwitz, Till Tantau

Publication date 10 November 2025

Copyright license Creative Commons Attribution 4.0 International

zbMATH Keywords

parameterized algorithmsgraph traversalgraph compressiontwinwidth

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 3582190 (Why is no real title available?)
• A SAT approach to twin-width
• A hybrid graph representation for recursive backtracking algorithms
• A nonrecursive list compacting algorithm
• A note on two problems in connexion with graphs
• A simple linear time algorithm for cograph recognition
• A strong-connectivity algorithm and its applications in data flow analysis
• Approximate distance oracles
• Deciding twin-width at most 4 is NP-complete
• Depth-first iterative-deepening: An optimal admissible tree search
• Edge-disjoint spanning trees and depth-first search
• Smallest-last ordering and clustering and graph coloring algorithms
• Twin-width and permutations (extended abstract)
• Twin-width and polynomial kernels
• Twin-width. I: Tractable FO model checking
• Weighted model counting with twin-width

Cited in

(1)

• Computing and certifying twin-width using logic

This page was built for publication: Faster graph algorithms through DAG compression

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