Linear time solvable optimization problems on graphs of bounded clique-width
From MaRDI portal
Publication:1974445
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
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
- Directed NLC-width
- MAD trees and distance-hereditary graphs
- The computational complexity of dominating set problems for instances with bounded minors of constraint matrices
- Recurrence relations for graph polynomials on bi-iterative families of graphs
- Recognizability, hypergraph operations, and logical types
- Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs
- On the parameterized complexity of reconfiguration of connected dominating sets
- Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
- A Logical Approach to Constraint Satisfaction
- Title not available (Why is that?)
- The complexity of some graph problems with bounded minors of their constraint matrices
- Title not available (Why is that?)
- Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes
- Algorithmic uses of the Feferman-Vaught theorem
- Graphs of separability at most 2
- Parameterized complexity of generalized domination problems
- Polynomial-time recognition of clique-width \(\leq 3\) graphs
- The maximum weight stable set problem in (\(P_6\), bull)-free graphs
- Complexity and approximability of parameterized MAX-CSPs
- Title not available (Why is that?)
- Vertex disjoint paths on clique-width bounded graphs
- Constrained-path labellings on graphs of bounded clique-width
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity
- Structure and stability number of chair-, co-P- and gem-free graphs revisited
- Well-quasi-ordering versus clique-width: new results on bigenic classes
- Faster algorithms for vertex partitioning problems parameterized by clique-width
- Clique-width and edge contraction
- Partitioning a graph into disjoint cliques and a triangle-free graph
- The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
- Clique-width of countable graphs: A compactness property.
- Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
- The complexity of finding uniform sparsest cuts in various graph classes
- Quadratic bottleneck knapsack problems
- Dominating induced matchings in graphs without a skew star
- On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width
- Colouring vertices of triangle-free graphs
- Graphs of separability at most two: structural characterizations and their consequences
- Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
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)
