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)
- 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
- MSOL partitioning problems on graphs of bounded treewidth and clique-width
- Solving some NP-complete problems using split decomposition
- Complexity of the packing coloring problem for trees
- Line graphs of bounded clique-width
- Dominating induced matchings for \(P_7\)-free graphs in linear time
- Automata for the verification of monadic second-order graph properties
- Critical hereditary graph classes: a survey
- Independent domination in finitely defined classes of graphs: polynomial algorithms
- Algorithms for propositional model counting
- 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 model-checking of monadic second-order formulas with edge set quantifications
- A characterisation of clique-width through nested partitions
- On the complexity of the dominating induced matching problem in hereditary classes of graphs
- Digraph width measures in parameterized algorithmics
- Finding a minimum path cover of a distance-hereditary graph in polynomial time
- On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
- (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
- NP-hard graph problems and boundary classes of graphs
- Equistable distance-hereditary graphs
- Approximating clique-width and branch-width
- Model counting for CNF formulas of bounded modular treewidth
- The VC-dimension of graphs with respect to \(k\)-connected subgraphs
- Linear layouts measuring neighbourhoods in graphs
- On the OBDD size for graphs of bounded tree- and clique-width
- Canonisation and Definability for Graphs of Bounded Rank Width
- The relative clique-width of a graph
- Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- Computations by fly-automata beyond monadic second-order logic
- Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
- THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES
- Ptolemaic Graphs and Interval Graphs Are Leaf Powers
- Dominating induced matchings
- Hereditary efficiently dominatable graphs
- Fly-automata for checking \(\mathrm{MSO}_2\) graph properties
- Enumeration of minimal dominating sets and variants
- Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
- Stability number of bull- and chair-free graphs revisited
- The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
- Algorithms parameterized by vertex cover and modular width, through potential maximal cliques
- Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
- Computing maximum stable sets for distance-hereditary graphs
- Fixed-parameter tractability of treewidth and pathwidth
- 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
- Computing the largest bond and the maximum connected cut of a graph
- 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
- Parameterized and approximation complexity of \textsc{Partial VC Dimension}
- Quantified conjunctive queries on partially ordered sets
- Quantified conjunctive queries on partially ordered sets
- A gentle introduction to applications of algorithmic metatheorems for space and circuit classes
- On strict (outer-)confluent graphs
- 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
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)
