Solving problems on graphs of high rank-width
type: Item
instance of: scholarly article
title: Solving problems on graphs of high rank-width
zbMATH Open document ID: 1390.68342
author: Eduard Eiben
author: Robert Ganian
author: Stefan Szeider
published in: Algorithmica
publication date: 2018-04-06T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6856558
zbMATH Keywords: fixed-parameter algorithms
zbMATH Keywords: rank-width
zbMATH Keywords: monadic second-order logic
zbMATH Keywords: parameterized complexity
Wikidata QID: Q93047965
MaRDI profile type: Publication
full work available at URL: s00453-017-0290-8
OpenAlex ID: W2258298398
cites work: Polynomial algorithm for finding the largest independent sets in graphs without forks
cites work: Boundary classes of graphs for the dominating set problem
cites work: Kernel Bounds for Path and Cycle Problems
cites work: Digraph Decompositions and Eulerian Systems
cites work: A note on \(\alpha\)-redundant vertices in graphs
cites work: Parameterized complexity of vertex colouring
cites work: On feedback vertex set: new measure and new structures
cites work: Chordal editing is fixed-parameter tractable
cites work: Linear time split decomposition revisited
cites work: Complement reducible graphs
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Vertex-minors, monadic second-order logic, and a conjecture by Seese
cites work: Decomposition of Directed Graphs
cites work: Parameterized Algorithms
cites work: Q4947393
cites work: Fundamentals of parameterized complexity
cites work: Meta-kernelization using Well-structured Modulators
cites work: Kernelization Using Structural Parameters on Sparse Graph Classes
cites work: On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
cites work: Meta-kernelization with Structural Parameters
cites work: Backdoors into heterogeneous classes of SAT and CSP
cites work: Distance labeling scheme and split decomposition
cites work: Robust algorithms for the stable set problem
cites work: Dynamic Distance Hereditary Graphs Using Split Decomposition
cites work: Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
cites work: Practical and efficient split decomposition via graph-labelled trees
cites work: Closing complexity gaps for coloring problems on \(H\)-free graphs
cites work: Finding Branch-Decompositions and Rank-Decompositions
cites work: The 3-Colorability Problem on Graphs with Maximum Degree Four
cites work: Q3353058
cites work: Elements of finite model theory.
cites work: Independent Set in P5-Free Graphs in Polynomial Time
cites work: Q5710169
cites work: Approximating clique-width and branch-width
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
DBLP publication ID: journals/algorithmica/EibenGS18
DOI: 10.1007/S00453-017-0290-8
description: scientific article; zbMATH DE number 6856558