A polynomial time algorithm to compute the connected treewidth of a series-parallel graph
DOI10.1016/j.dam.2021.02.039OpenAlexW3155448334MaRDI QIDQ831866
Dimitrios M. Thilikos, Guillaume Mescoff, Christophe Paul
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
dynamic programmingtreewidthseries-parallel graphscombinatorial algorithmsgraph classesgraph decompositionsconnected treewidthwidth parameters
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Games involving graphs (91A43) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Connected graph searching
- Graph minors. III. Planar tree-width
- Monotony properties of connected visible graph searching
- Interval graphs and searching
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- The vertex separation number of a graph equals its path-width
- Parallel recognition of series-parallel graphs
- S-functions for graphs
- Graph searching and a min-max theorem for tree-width
- The combinations of resistances.
- Fugitive-search games on graphs and related parameters
- Searching and pebbling
- Finding small-width connected path decompositions in polynomial time
- Topology of series-parallel networks
- Nonserial dynamic programming
- Monotony Properties of Connected Visible Graph Searching
- Connected Treewidth and Connected Graph Searching
- Complexity of Finding Embeddings in a k-Tree
- Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs
- The Recognition of Series Parallel Digraphs
- Monotonicity in graph searching
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- Linear-time computation of optimal subgraphs of decomposable graphs
- From Pathwidth to Connected Pathwidth
- A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth
- Connected Search for a Lazy Robber
- Graph-Theoretic Concepts in Computer Science
This page was built for publication: A polynomial time algorithm to compute the connected treewidth of a series-parallel graph
