A polynomial time algorithm to compute the connected treewidth of a series-parallel graph

DOI10.1016/J.DAM.2021.02.039MaRDI QIDQ831866zbMATH OpenOpenAlexFDO

Authors Guillaume Mescoff, Christophe Paul, Dimitrios M. Thilikos

Publication date 24 March 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2021.02.039

zbMATH Keywords

combinatorial algorithmsconnected treewidthdynamic programminggraph classesgraph decompositionsseries-parallel graphstreewidthwidth parameters

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Games involving graphs (91A43)

Recommendations

• Connected Treewidth and Connected Graph Searching
• From pathwidth to connected pathwidth
• Connected graph searching in chordal graphs
• From pathwidth to connected pathwidth
• A linear fixed parameter tractable algorithm for connected pathwidth

Cites work

• A linear fixed parameter tractable algorithm for connected pathwidth
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Complexity of Finding Embeddings in a k-Tree
• Connected graph searching
• Connected Search for a Lazy Robber
• Connected Treewidth and Connected Graph Searching
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs
• Finding small-width connected path decompositions in polynomial time
• From pathwidth to connected pathwidth
• Fugitive-search games on graphs and related parameters
• Graph minors. III. Planar tree-width
• Graph searching and a min-max theorem for tree-width
• scientific article; zbMATH DE number 4147519 (Why is no real title available?)
• scientific article; zbMATH DE number 3590298 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Interval graphs and searching
• Linear-time computation of optimal subgraphs of decomposable graphs
• Monotonicity in graph searching
• Monotony properties of connected visible graph searching
• Monotony Properties of Connected Visible Graph Searching
• Nonserial dynamic programming
• Parallel recognition of series-parallel graphs
• S-functions for graphs
• Searching and pebbling
• Searching is not jumping.
• The combinations of resistances.
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• The Recognition of Series Parallel Digraphs
• The vertex separation number of a graph equals its path-width
• Topology of series-parallel networks

Cited in

(2)

• A linear fixed parameter tractable algorithm for connected pathwidth
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

This page was built for publication: A polynomial time algorithm to compute the connected treewidth of a series-parallel graph

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