Finding edge-disjoint paths in partial \(k\)-trees
type: Item
instance of: scholarly article
title: Finding edge-disjoint paths in partial \(k\)-trees
zbMATH Open document ID: 0951.68100
author: Yanyan Li
published in: Algorithmica
publication date: 2000-12-12T00:00:00Z
review text: For a given graph \(G\) and \(p\) pairs \((s_i,t_i)\), \(1\leq i\leq p\), of vertices of \(G\), the edge-disjoint paths problem is to find \(p\) pairwise edge-disjoint paths \(P_i\), \(1\leq i \leq p\), connecting \(s_i\) and \(t_i\). This paper gives two algorithms for the edge-disjoint paths problem on partial \(k\)-trees. The first one solves the problem for any partial \(k\)-tree \(G\) and runs in polynomial time if \(p=O(\log n)\) and in linear time if \(p=O(1)\), where \(n\) is the number of vertices in \(G\). The second one solves the problem under some restrictions on the location of terminal pairs even if \(p\geq \log n\).
reviewed by: Klaus Dohmen
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W05
zbMATH DE Number: 1417529
zbMATH Keywords: edge-disjoint paths
zbMATH Keywords: partial \(k\)-tree
zbMATH Keywords: treewidth
zbMATH Keywords: edge-coloring
MaRDI profile type: Publication
full work available at URL: s004539910002
OpenAlex ID: W2046202598
DOI: 10.1007/S004539910002
description: scientific article; zbMATH DE number 1417529