Linear time solvable optimization problems on graphs of bounded clique-width

DOI10.1007/S002249910009zbMATH Open1009.68102OpenAlexW2053991811WikidataQ56474999 ScholiaQ56474999MaRDI QIDQ1974445FDOQ1974445

Authors: Udi Rotics, Johann A. Makowsky, Bruno Courcelle 

Publication date: 18 March 2003

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.3501

Recommendations

• scientific article; zbMATH DE number 1262783
• Polynomial-time recognition of clique-width \(\leq 3\) graphs
• scientific article; zbMATH DE number 1953082

zbMATH Keywords

hierarchical decomposition of graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Cited In (only showing first 100 items - show all)

• Trees, grids, and MSO decidability: from graphs to matroids
• A parameterized complexity view on collapsing \(k\)-cores
• Tree pivot-minors and linear rank-width
• Title not available (Why is that?)
• On low rank-width colorings
• Computing the zig-zag number of directed graphs
• Are there any good digraph width measures?
• Computing the largest bond and the maximum connected cut of a graph
• Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width
• Packing disjoint cycles over vertex cuts
• Quantified conjunctive queries on partially ordered sets
• Quantified conjunctive queries on partially ordered sets
• Low-congestion shortcut and graph parameters
• On strict (outer-)confluent graphs
• A polynomial kernel for 3-leaf power deletion
• Structure and algorithms for (cap, even hole)-free graphs
• First-order interpretations of bounded expansion classes
• Notes on complexity of packing coloring
• On the computational complexity of the bipartizing matching problem
• Upper domination: towards a dichotomy through boundary properties
• Well-quasi-ordering versus clique-width: new results on bigenic classes
• Compact representation of graphs of small clique-width
• On list \(k\)-coloring convex bipartite graphs
• Feedback vertex set on AT-free graphs
• A local characterization of bounded clique-width for line graphs
• Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
• Comparing linear width parameters for directed graphs
• Colouring square-free graphs without long induced paths
• Boundary classes for graph problems involving non-local properties
• Colouring diamond-free graphs
• Secure total domination in chain graphs and cographs
• Algorithms for unipolar and generalized split graphs
• Triple Roman domination in graphs
• The NLC-width and clique-width for powers of graphs of bounded tree-width
• Meta-kernelization with structural parameters
• Graph classes with and without powers of bounded clique-width
• The complexity of power indexes with graph restricted coalitions
• Clique-width for graph classes closed under complementation
• Solving problems on graphs of high rank-width
• On exact solution approaches for the longest induced path problem
• Rank-width: algorithmic and structural results
• Classifying the clique-width of \(H\)-free bipartite graphs
• The recognizability of sets of graphs is a robust property
• Graph Operations Characterizing Rank-Width and Balanced Graph Expressions
• Mind the independence gap
• Grundy dominating sequences on \(X\)-join product
• Partial complementation of graphs
• Graphs vertex-partitionable into strong cliques
• On the complexity of \(\{k\}\)-domination and \(k\)-tuple domination in graphs
• Parameterized leaf power recognition via embedding into graph products
• Clique-width of graph classes defined by two forbidden induced subgraphs
• Bounding the clique-width of \(H\)-free chordal graphs
• On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph
• Counting spanning trees using modular decomposition
• Digraphs of bounded elimination width
• Title not available (Why is that?)
• Latency-bounded target set selection in social networks
• A slice theoretic approach for embedding problems on digraphs
• Polynomial algorithms for protein similarity search for restricted mRNA structures
• Complexity of the Packing Coloring Problem for Trees
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• Graph classes with structured neighborhoods and algorithmic applications
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
• Branch-width, parse trees, and monadic second-order logic for matroids.
• Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
• Practical algorithms for MSO model-checking on tree-decomposable graphs
• GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH
• Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
• Towards fixed-parameter tractable algorithms for abstract argumentation
• Regular independent sets
• An algorithmic metatheorem for directed treewidth
• Clique-width of path powers
• Graph partitions with prescribed patterns
• On polynomial kernels for structural parameterizations of odd cycle transversal
• Minimal classes of graphs of unbounded clique-width
• Courcelle's theorem -- a game-theoretic approach
• Graphs of linear clique-width at most 3
• Are there any good digraph width measures?
• Tree-width and the monadic quantifier hierarchy.
• \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth
• On a disparity between relative cliquewidth and relative NLC-width
• Recent developments on graphs of bounded clique-width
• On the structure of (\(P_{5}\),\,gem)-free graphs
• GETGRATS: a summary of scientific results (with annotated bibliography)
• Edge dominating set and colorings on graphs with fixed clique-width
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• Clique cycle-transversals in distance-hereditary graphs
• Between treewidth and clique-width
• The Clique-Width of Tree-Power and Leaf-Power Graphs
• Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
• On structural parameterizations of star coloring
• Efficient algorithms for Roman domination on some classes of graphs
• Algorithmic meta-theorems for restrictions of treewidth
• Computing the clique-width of large path powers in linear time via a new characterisation of clique-width
• Tight complexity bounds for FPT subgraph problems parameterized by clique-width
• Graph classes with structured neighborhoods and algorithmic applications
• On the clique-width of some perfect graph classes
• Boolean-width of graphs
• On algorithms for (\(P_5\), gem)-free graphs

This page was built for publication: Linear time solvable optimization problems on graphs of bounded clique-width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1974445)