Typical sequences revisited -- computing width parameters of graphs

DOI10.1007/s00224-021-10030-3OpenAlexW3150373505WikidataQ126176055 ScholiaQ126176055MaRDI QIDQ2701067

Jan Arne Telle, Lars Jaffke, Hans L. Bodlaender

Publication date: 27 April 2023

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-021-10030-3

zbMATH Keywords

treewidthcutwidthmodified cutwidthseries parallel digraphstypical sequences

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx) Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for treewidth
• Derivation of algorithms for cutwidth and related graph layout parameters
• Graph minors. XIII: The disjoint paths problem
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Faster Computation of Path-Width
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• The Recognition of Series Parallel Digraphs
• Complete Register Allocation Problems
• Scheduling expression DAGs for minimal register need
• The “Art of Trellis Decoding” Is Fixed-Parameter Tractable
• Constructive linear time algorithms for branchwidth
• Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Parameterized and Exact Computation
• Cutwidth I: A linear time fixed parameter algorithm
• Cutwidth II: Algorithms for partial w-trees of bounded degree
• The Generation of Optimal Code for Arithmetic Expressions
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Typical sequences revisited -- computing width parameters of graphs