scientific article; zbMATH DE number 7205205

DOI10.4230/LIPIcs.IPEC.2017.21zbMath1443.68131arXiv1708.04536MaRDI QIDQ5111880

Jan Arne Telle, O-joung Kwon, Lars Jaffke

Publication date: 27 May 2020

Full work available at URL: https://arxiv.org/abs/1708.04536

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

dynamic programminggraph classesinduced pathsgraph width parametersinduced topological minors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

Unnamed Item ⋮ Mim-width. I. Induced path problems ⋮ On the tractability of optimization problems on \(H\)-graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Mim-width. II. The feedback vertex set problem ⋮ Mim-width. III. Graph powers and generalized distance domination problems

Cites Work

• Graph classes with structured neighborhoods and algorithmic applications
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• An improved algorithm for the longest induced path problem on \(k\)-chordal graphs
• Algorithms for maximum weight induced paths
• A width parameter useful for chordal and co-comparability graphs
• Graph minors. XIII: The disjoint paths problem
• Induced disjoint paths in AT-free graphs
• Mim-width. III. Graph powers and generalized distance domination problems
• The \(k\)-in-a-path problem for claw-free graphs
• Induced disjoint paths in circular-arc graphs in linear time
• The point-set embeddability problem for plane graphs
• The Induced Disjoint Paths Problem
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Hardness of computing width parameters based on branch decompositions over the vertex set
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: