scientific article

DOI10.4230/LIPICS.STACS.2018.42zbMath1487.68180arXiv1710.07148MaRDI QIDQ3304141

O-joung Kwon, Jan Arne Telle, Lars Jaffke

Publication date: 5 August 2020

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

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

zbMATH Keywords

feedback vertex setgraph classesleaf powersgraph width parameters

Mathematics Subject Classification ID

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

Related Items (10)

Mim-width. I. Induced path problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Mim-width. II. The feedback vertex set problem ⋮ Subset feedback vertex set on graphs of bounded independent set size ⋮ Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth. ⋮ Mim-width. III. Graph powers and generalized distance domination problems ⋮ Node multiway cut and subset feedback vertex set on graphs of bounded mim-width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Clique-width of path powers
• Towards a characterization of leaf powers by clique arrangements
• Graph classes with structured neighborhoods and algorithmic applications
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Feedback vertex set on AT-free graphs
• Improved algorithms for feedback vertex set problems
• Feedback vertex set on graphs of low clique-width
• On polygon numbers of circle graphs and distance hereditary graphs
• Faster fixed parameter tractable algorithms for finding feedback vertex sets
• Intractability of Clique-Width Parameterizations
• Pairwise Compatibility Graphs: A Survey
• ON DISJOINT CYCLES
• Hamilton Paths in Grid Graphs
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Reducibility among Combinatorial Problems
• Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• Parameterized and Exact Computation
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Computing and Combinatorics
• Hardness of computing width parameters based on branch decompositions over the vertex set
• An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width

This page was built for publication: