A Bound on the Pathwidth of Sparse Graphs with Applications to Exact Algorithms

DOI10.1137/080715482zbMath1219.05187OpenAlexW2081438146MaRDI QIDQ5189527

Stefan Richter, Joachim Kneis, Daniel Mölle, Peter Rossmanith

Publication date: 17 March 2010

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/080715482

zbMATH Keywords

algorithmgraph theorygraph algorithmspathwidth

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) General topics in the theory of algorithms (68W01)

Related Items

Bounds for the Twin-Width of Graphs, Fixed-Parameter Tractability of Treewidth and Pathwidth, Improved exact algorithms for mildly sparse instances of MAX SAT, Parameterized and approximation algorithms for the load coloring problem, Space saving by dynamic algebraization based on tree-depth, A faster polynomial-space algorithm for Max 2-CSP, Solving sparse instances of Max SAT via width reduction and greedy restriction, A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP, Improved FPT Algorithms for Deletion to Forest-Like Structures., The Asymmetric Travelling Salesman Problem In Sparse Digraphs., Inclusion/exclusion meets measure and conquer, Unnamed Item, $K_4$-Minor-Free Induced Subgraphs of Sparse Connected Graphs