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)
- 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.
- Clique-width with an inactive label
- Characterizations for restricted graphs of NLC-width 2
- On some domination colorings of graphs
- Independent domination in finitely defined classes of graphs
- Graph operations characterizing rank-width
- Title not available (Why is that?)
- Confronting intractability via parameters
- A boundary property for upper domination
- Upper domination: complexity and approximation
- Well-quasi-ordering does not imply bounded clique-width
- On digraph width measures in parameterized algorithmics
- From tree-decompositions to clique-width terms
- Monadic Second-Order Logic for Graphs: Algorithmic and Language Theoretical Applications
- Compact labelings for efficient first-order model-checking
- Graph decomposition of slim graphs
- Chordal bipartite graphs of bounded tree- and clique-width
- On the relationship between NLC-width and linear NLC-width
- Rank-width of random graphs
- Farrell polynomials on graphs of bounded tree width
- Parameterized algorithms for the independent set problem in some hereditary graph classes
- Bounding clique-width via perfect graphs
- Algorithms for Propositional Model Counting
- Linear clique-width for hereditary classes of cographs
- The complexity of the matching-cut problem for planar graphs and other graph classes
- On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
- Title not available (Why is that?)
- Linear-time algorithms for graphs of bounded rankwidth: a fresh look using game theory (extended abstract)
- Graphs of Linear Clique-Width at Most 3
- Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
- On the structure of graphs without claw, \(4K_1\) and co-R
- The rank-width of edge-coloured graphs
- A new graph construction of unbounded clique-width
- Title not available (Why is that?)
- The behavior of clique-width under graph operations and graph transformations
- Obstructions for linear rank-width at most 1
- The computational complexity of three graph problems for instances with bounded minors of constraint matrices
- 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
- In)approximability of Maximum Minimal FVS
- 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
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)
