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
• Coloring vertices of claw-free graphs in three colors
• Solving larger maximum clique problems using parallel quantum annealing
• Colouring square-free graphs without long induced paths
• Finer tight bounds for coloring on clique-width
• Finer tight bounds for coloring on clique-width
• Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs
• Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
• A gentle introduction to applications of algorithmic metatheorems for space and circuit classes
• On strict (outer-)confluent graphs
• The factorisation forest theorem
• Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs
• Well-quasi-ordering versus clique-width
• FO model checking on geometric graphs
• Parameterized complexity of geodetic set
• 4-coloring \((P_6, \text{bull})\)-free graphs
• The complexity landscape of decompositional parameters for ILP
• Parameterized model checking of rendezvous systems
• FO model checking of geometric graphs
• Bounding clique-width via perfect graphs
• Parameterized orientable deletion
• Parameterized (approximate) defective coloring
• On efficient domination for some classes of \(H\)-free chordal graphs
• Reasoning about integrity constraints for tree-structured data
• Complexity of \(k\)-tuple total and total \(\{k\}\)-dominations for some subclasses of bipartite graphs
• On width measures and topological problems on semi-complete digraphs
• Parameterized (approximate) defective coloring
• Total Roman \(\{2\}\)-dominating functions in graphs
• On the width of regular classes of finite structures
• Branch-depth: generalizing tree-depth of graphs
• Containment of monadic Datalog programs via bounded clique-width
• Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Maximum matching in almost linear time on graphs of bounded clique-width
• The power of cut-based parameters for computing edge-disjoint paths
• U-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
• Grundy distinguishes treewidth from pathwidth
• (In)approximability of maximum minimal FVS
• Meta-kernelization using well-structured modulators

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)