Solving some NP-complete problems using split decomposition
type: Item
instance of: scholarly article
title: Solving some NP-complete problems using split decomposition
zbMATH Open document ID: 1155.05058
author: Michaël Rao
published in: Discrete Applied Mathematics
publication date: 2008-10-17T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 5353569
zbMATH Keywords: graph algorithms
zbMATH Keywords: graph coloring
zbMATH Keywords: NP-complete problems
zbMATH Keywords: split decomposition
zbMATH Keywords: clique-width
MaRDI profile type: MaRDI publication profile
full work available at URL: j.dam.2007.11.013
OpenAlex ID: W2026055698
cites work: Easy problems for tree-decomposable graphs
cites work: Q3222223
cites work: On algorithms for (\(P_5\), gem)-free graphs
cites work: Q4500843
cites work: Computing the treewidth and the minimum fill-in with the modular decomposition
cites work: On the structure of (\(P_{5}\),\,gem)-free graphs
cites work: The strong perfect graph theorem
cites work: On the extension of bipartite to parity graphs
cites work: Handle-rewriting hypergraph grammars
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Upper bounds to the clique width of graphs
cites work: Q4954442
cites work: Decomposition of Directed Graphs
cites work: Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
cites work: Q4448752
cites work: Recognizing circle graphs in polynomial time
cites work: Q3216686
cites work: Completely separable graphs
cites work: Edge dominating set and colorings on graphs with fixed clique-width
cites work: An O(n2) Algorithm for Undirected Split Decomposition
cites work: Modular decomposition and transitive orientation
cites work: Q3683903
cites work: Recognition of Circle Graphs
cites work: Decomposition by clique separators
cites work: Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
DOI: 10.1016/J.DAM.2007.11.013
description: scientific article; zbMATH DE number 5353569