Linear time solvable optimization problems on graphs of bounded clique-width
From MaRDI portal
Publication:1974445
DOI10.1007/s002249910009zbMath1009.68102OpenAlexW2053991811WikidataQ56474999 ScholiaQ56474999MaRDI QIDQ1974445
Bruno Courcelle, Udi Rotics, Johann A. Makowsky
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
Related Items
Complexity of the Packing Coloring Problem for Trees, On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width, Hereditary Efficiently Dominatable Graphs, Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem, Unnamed Item, Grundy Distinguishes Treewidth from Pathwidth, On the minimum cycle cover problem on graphs with bounded co-degeneracy, On the outer independent total double Roman domination in graphs, A polynomial kernel for 3-leaf power deletion, Fair allocation algorithms for indivisible items under structured conflict constraints, On the parameterized complexity of the structure of lineal topologies (depth-first spanning trees) of finite graphs: the number of leaves, Clique‐width: Harnessing the power of atoms, A Framework for Minimal Hereditary Classes of Graphs of Unbounded Clique-Width, A class of graphs with large rankwidth, THE MINIMAL DOMINATING SETS IN A DIRECTED GRAPH AND THE KEY INDICATORS SET OF SOCIO–ECONOMIC SYSTEM, First-order Logic with Connectivity Operators, Linear‐time algorithms for eliminating claws in graphs, Solving larger maximum clique problems using parallel quantum annealing, Parameterized (Approximate) Defective Coloring, Grouped domination parameterized by vertex cover, twin cover, and beyond, Feferman-vaught decompositions for prefix classes of first order logic, Parameterized complexity for iterated type partitions and modular-width, On structural parameterizations of star coloring, Treewidth versus clique number. II: Tree-independence number, Stability, vertex stability, and unfrozenness for special graph classes, Unnamed Item, Unnamed Item, Clique-Width for Graph Classes Closed under Complementation, Extended MSO model checking via small vertex integrity, Some new algorithmic results on co-secure domination in graphs, Three remarks on \(\mathbf{W}_{\mathbf{2}}\) graphs, Unnamed Item, Unnamed Item, Unnamed Item, Finer Tight Bounds for Coloring on Clique-Width, GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH, First-Order Model-Checking in Random Graphs and Complex Networks, In)approximability of Maximum Minimal FVS, Parameterized Complexity of Graph Burning, Contracting to a longest path in H-free graphs, Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, Unnamed Item, Unnamed Item, Parameterized aspects of triangle enumeration, Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs, Clique-width and well-quasi-ordering of triangle-free graph classes, On low rank-width colorings, Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs, Computations by fly-automata beyond monadic second-order logic, An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width, A polynomial kernel for distance-hereditary vertex deletion, Ptolemaic Graphs and Interval Graphs Are Leaf Powers, Clique-width of point configurations, Unnamed Item, Exploring the gap between treedepth and vertex cover through vertex integrity, Unnamed Item, On efficient domination for some classes of \(H\)-free chordal graphs, On efficient domination for some classes of \(H\)-free chordal graphs, Graph functionality, On structural parameterizations of firefighting, Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth., Uniformly Automatic Classes of Finite Structures, Unnamed Item, Partial complementation of graphs, ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES, A Logical Approach to Constraint Satisfaction, Node multiway cut and subset feedback vertex set on graphs of bounded mim-width, Quadruple Roman domination in graphs, Parameterized Complexity of Geodetic Set, Critical elements in combinatorially closed families of graph classes, Canonisation and Definability for Graphs of Bounded Rank Width, An algorithmic metatheorem for directed treewidth, Clique-width of path powers, Characterizations for co-graphs defined by restricted NLC-width or clique-width operations, Trees, grids, and MSO decidability: from graphs to matroids, A parameterized complexity view on collapsing \(k\)-cores, Computing the zig-zag number of directed graphs, On the parameterized complexity of reconfiguration of connected dominating sets, Clique cycle-transversals in distance-hereditary graphs, FO model checking on geometric graphs, Between treewidth and clique-width, Parameterized model checking of rendezvous systems, Notes on complexity of packing coloring, Fly-automata for checking monadic second-order properties of graphs of bounded tree-width, Some links between identifying codes and separating, dominating and total dominating sets in graphs, A complexity dichotomy and a new boundary class for the dominating set problem, On the complexity of rainbow coloring problems, Model counting for CNF formulas of bounded modular treewidth, The VC-dimension of graphs with respect to \(k\)-connected subgraphs, Reasoning about integrity constraints for tree-structured data, Complexity of \(k\)-tuple total and total \(\{k\}\)-dominations for some subclasses of bipartite graphs, A local characterization of bounded clique-width for line graphs, The computational complexity of dominating set problems for instances with bounded minors of constraint matrices, Characterizations for restricted graphs of NLC-width 2, Algorithmic uses of the Feferman-Vaught theorem, A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion, Complexity classification of the edge coloring problem for a family of graph classes, MSOL partitioning problems on graphs of bounded treewidth and clique-width, Tight complexity bounds for FPT subgraph problems parameterized by the clique-width, 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, Structure and algorithms for (cap, even hole)-free graphs, Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity, Farrell polynomials on graphs of bounded tree width, Courcelle's theorem -- a game-theoretic approach, Are there any good digraph width measures?, Meta-kernelization with structural parameters, Graph classes with and without powers of bounded clique-width, Independent domination in finitely defined classes of graphs, Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences, Tree-width and the monadic quantifier hierarchy., Graphs of separability at most 2, Parameterized complexity of generalized domination problems, Polynomial-time recognition of clique-width \(\leq 3\) graphs, On the model-checking of monadic second-order formulas with edge set quantifications, The complexity of power indexes with graph restricted coalitions, Compact labelings for efficient first-order model-checking, Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time, Stability number of bull- and chair-free graphs revisited, MAD trees and distance-hereditary graphs, Directed NLC-width, Classifying the clique-width of \(H\)-free bipartite graphs, Induced minor free graphs: isomorphism and clique-width, The many facets of upper domination, On the structure and stability number of \(P_{5}\)- and co-chair-free graphs, Graphs vertex-partitionable into strong cliques, Solving problems on graphs of high rank-width, The complexity of finding uniform sparsest cuts in various graph classes, Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number, Clique-width of countable graphs: A compactness property., Clique-width with an inactive label, Confronting intractability via parameters, (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization., Practical algorithms for MSO model-checking on tree-decomposable graphs, Dominating induced matchings for \(P_7\)-free graphs in linear time, Minimal classes of graphs of unbounded clique-width, Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs, Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs, Parameterized and approximation complexity of \textsc{Partial VC Dimension}, On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size, Feedback vertex set on AT-free graphs, Solving some NP-complete problems using split decomposition, A new graph construction of unbounded clique-width, Critical hereditary graph classes: a survey, The behavior of clique-width under graph operations and graph transformations, Recent developments on graphs of bounded clique-width, Complexity of the packing coloring problem for trees, \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth, On a disparity between relative cliquewidth and relative NLC-width, On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width, Packing disjoint cycles over vertex cuts, On the complexity of the dominating induced matching problem in hereditary classes of graphs, Boolean-width of graphs, Graphs of linear clique-width at most 3, 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, Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity, Efficient algorithms for Roman domination on some classes of graphs, Structure and stability number of chair-, co-P- and gem-free graphs revisited, Recurrence relations for graph polynomials on bi-iterative families of graphs, Algorithms for unipolar and generalized split graphs, On the OBDD size for graphs of bounded tree- and clique-width, The NLC-width and clique-width for powers of graphs of bounded tree-width, Graph operations characterizing rank-width, Mind the independence gap, Grundy dominating sequences on \(X\)-join product, Parameterized leaf power recognition via embedding into graph products, Regular independent sets, On algorithms for (\(P_5\), gem)-free graphs, Iterated Type Partitions, On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal, Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width, Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics, Rank-width of random graphs, Computing L(p,1)-Labeling with Combined Parameters, Parameterized Complexity of Geodetic Set, Containment of Monadic Datalog Programs via Bounded Clique-Width, Solving Problems on Graphs of High Rank-Width, On the Equivalence among Problems of Bounded Width, Unnamed Item, Quantified conjunctive queries on partially ordered sets, Fixed-Parameter Tractability of Treewidth and Pathwidth, The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs, The relative clique-width of a graph, Clique-perfectness and balancedness of some graph classes, The power of cut-based parameters for computing edge-disjoint paths, Triple Roman domination in graphs, On Strict (Outer-)Confluent Graphs, Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs, Finding a maximum minimal separator: graph classes and fixed-parameter tractability, Computing the largest bond and the maximum connected cut of a graph, Colouring square-free graphs without long induced paths., Between Treewidth and Clique-Width, Quantified Conjunctive Queries on Partially Ordered Sets, Bounding the Clique-Width of H-free Chordal Graphs, A SAT Approach to Clique-Width, Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs, Unique key Horn functions, Algorithms for Propositional Model Counting, On the computational complexity of the bipartizing matching problem, Graphs of Linear Clique-Width at Most 3, Computing densest \(k\)-subgraph with structural parameters, Parameterized complexity of envy-free resource allocation in social networks, Graph Operations Characterizing Rank-Width and Balanced Graph Expressions, The Clique-Width of Tree-Power and Leaf-Power Graphs, Unnamed Item, Unnamed Item, Domination and convexity problems in the target set selection model, Unnamed Item, On the structure of (pan, even hole)‐free graphs, On the complexity of the labeled domination problem in graphs, Unnamed Item, On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs, Perfectly matched sets in graphs: parameterized and exact computation, THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES, Linear Clique‐Width for Hereditary Classes of Cographs, Unnamed Item, How Bad is the Freedom to Flood-It?, Faster algorithms for vertex partitioning problems parameterized by clique-width, Finding a minimum path cover of a distance-hereditary graph in polynomial time, Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes, Graphs of Separability at Most Two: Structural Characterizations and Their Consequences, Model checking existential logic on partially ordered sets, Line graphs of bounded clique-width, Parameterized Leaf Power Recognition via Embedding into Graph Products, Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width, NP-hard graph problems and boundary classes of graphs, Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width, Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory, Acyclic polynomials of graphs, Equistable distance-hereditary graphs, GETGRATS, Graph Operations, Graph Transformations and Monadic Second-Order Logic:, Unnamed Item, Branch-width, parse trees, and monadic second-order logic for matroids., The monadic second-order logic of graphs. XV: On a conjecture by D. Seese, Approximating clique-width and branch-width, Recognizability, hypergraph operations, and logical types, Linear layouts measuring neighbourhoods in graphs, Vertex disjoint paths on clique-width bounded graphs, Colouring Vertices of Triangle-Free Graphs, Are There Any Good Digraph Width Measures?, Graph partitions with prescribed patterns, Bounding Clique-Width via Perfect Graphs, Secure total domination in chain graphs and cographs, Monadic Second-Order Logic for Graphs: Algorithmic and Language Theoretical Applications, Counting Spanning Trees in Graphs Using Modular Decomposition, Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs, Enumeration of Minimal Dominating Sets and Variants, A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs, A Boundary Property for Upper Domination, Upper Domination: Complexity and Approximation, Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes, Well-quasi-ordering Does Not Imply Bounded Clique-width, A Slice Theoretic Approach for Embedding Problems on Digraphs, Graph Classes with Structured Neighborhoods and Algorithmic Applications, The complexity of the matching-cut problem for planar graphs and other graph classes, Dominating Induced Matchings, The Exact Weighted Independent Set Problem in Perfect Graphs and Related Classes, On Digraph Width Measures in Parameterized Algorithmics, Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs, The recognizability of sets of graphs is a robust property, Computing maximum stable sets for distance-hereditary graphs, Digraphs of Bounded Width, Unnamed Item, On the relationship between NLC-width and linear NLC-width, Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure, Unnamed Item, Tree Pivot-Minors and Linear Rank-Width, Quadratic bottleneck knapsack problems, The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions., Uncountably many minimal hereditary classes of graphs of unbounded clique-width, Algorithms for vertex-partitioning problems on graphs with fixed clique-width., Vertex coloring \((4K_1\), hole-twin, 5-wheel)-free graphs, Identifying codes in the complementary prism of cycles, Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs, Polynomial algorithms for protein similarity search for restricted mRNA structures, Directed width parameters on semicomplete digraphs, Total Roman \(\{2\}\)-dominating functions in graphs, A general framework for path convexities, On the structure of graphs without claw, \(4K_1\) and co-R, The rank-width of edge-coloured graphs, Parameterized complexity of graph burning, On some domination colorings of graphs, Boundary classes for graph problems involving non-local properties, Colouring diamond-free graphs, Distance from triviality 2.0: hybrid parameterizations, Rank-width: algorithmic and structural results, 4-coloring \((P_6, \text{bull})\)-free graphs, The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring, Parameterized complexity of fair deletion problems, Grammars and clique-width bounds from split decompositions, On quasi-planar graphs: clique-width and logical description, An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion, Complexity and approximability of parameterized MAX-CSPs, Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs, More results on weighted independent domination, Subgraph complementation, Parameterized orientable deletion, Parameterized edge Hamiltonicity, From tree-decompositions to clique-width terms, Infinitely many minimal classes of graphs of unbounded clique-width, Meta-kernelization using well-structured modulators, Linear-time algorithms for three domination-based separation problems in block graphs, Structural parameters, tight bounds, and approximation for \((k, r)\)-center, Bounding clique-width via perfect graphs, Automata for the verification of monadic second-order graph properties, On strict (outer-)confluent graphs, Counting spanning trees using modular decomposition, Complexity and algorithms for recognizing polar and monopolar graphs, Obstructions for linear rank-width at most 1, Digraphs of bounded elimination width, Digraph width measures in parameterized algorithmics, Constrained-path labellings on graphs of bounded clique-width, Dominating induced matchings in graphs without a skew star, Latency-bounded target set selection in social networks, Branch-depth: generalizing tree-depth of graphs, Classes of graphs with low complexity: the case of classes with bounded linear rankwidth, A gentle introduction to applications of algorithmic metatheorems for space and circuit classes, Efficient computation of the oriented chromatic number of recursively defined digraphs, Polynomial-time algorithm for isomorphism of graphs with clique-width at most three, Low-congestion shortcut and graph parameters, Well-quasi-ordering versus clique-width, The complexity landscape of decompositional parameters for ILP, Maximal double Roman domination in graphs, Algorithms parameterized by vertex cover and modular width, through potential maximal cliques, Fly-automata for checking \(\mathrm{MSO}_2\) graph properties, Coloring vertices of claw-free graphs in three colors, On exact solution approaches for the longest induced path problem, Algorithmic meta-theorems for restrictions of treewidth, Independent domination in finitely defined classes of graphs: polynomial algorithms, Towards fixed-parameter tractable algorithms for abstract argumentation, On the structure of (\(P_{5}\),\,gem)-free graphs, Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width, Algorithms for propositional model counting, On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph, Measuring what matters: a hybrid approach to dynamic programming with treewidth, On \textsf{NC} algorithms for problems on bounded rank-width graphs, Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs, (In)approximability of maximum minimal FVS, Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width, On the width of regular classes of finite structures, On list \(k\)-coloring convex bipartite graphs, Computing a metric basis of a bipartite distance-hereditary graph, Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width, On width measures and topological problems on semi-complete digraphs, \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited, Chordal bipartite graphs of bounded tree- and clique-width, The factorisation forest theorem, Comparing linear width parameters for directed graphs, Colouring square-free graphs without long induced paths, On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem, New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs, On efficient domination for some classes of \(H\)-free bipartite graphs, Revising Johnson's table for the 21st century, Optimal centrality computations within bounded clique-width graphs, Twin-width and polynomial kernels, Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds, Maximum matching in almost linear time on graphs of bounded clique-width, Restrained condition on double Roman dominating functions, Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time., Clique-width of full bubble model graphs, On the complexity of \(\{k\}\)-domination and \(k\)-tuple domination in graphs, Edge dominating set and colorings on graphs with fixed clique-width, A characterisation of clique-width through nested partitions, Clique-width and edge contraction, Partitioning a graph into disjoint cliques and a triangle-free graph, Vertex cover at distance on \(H\)-free graphs, The computational complexity of three graph problems for instances with bounded minors of constraint matrices
