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)
- 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
- 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
- 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 the width of regular classes of finite structures
- Containment of monadic Datalog programs via bounded clique-width
- Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs
- Maximum matching in almost linear time on graphs of bounded clique-width
- A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
- Complexity classification of the edge coloring problem for a family of graph classes
- On \textsf{NC} algorithms for problems on bounded rank-width graphs
- The exact weighted independent set problem in perfect graphs and related classes
- Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity
- Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
- The many facets of upper domination
- Extension complexity, MSO logic, and treewidth
- On the structure of (pan, even hole)-free graphs
- An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion
- Complexity and algorithms for recognizing polar and monopolar graphs
- Parameterized Complexity of Geodetic Set
- Model checking existential logic on partially ordered sets
- Induced minor free graphs: isomorphism and clique-width
- Parameterized complexity of fair deletion problems
- Digraphs of bounded width
- Solving problems on graphs of high rank-width
- New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs
- A slice theoretic approach for embedding problems on digraphs
- Parameterized aspects of triangle enumeration
- An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width
- Domination and convexity problems in the target set selection model
- Polynomial-time algorithm for isomorphism of graphs with clique-width at most three
- Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
- On the outer independent total double Roman domination in graphs
- Infinitely many minimal classes of graphs of unbounded clique-width
- Computing densest \(k\)-subgraph with structural parameters
- Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
- Critical elements in combinatorially closed families of graph classes
- Vertex cover at distance on \(H\)-free graphs
- Maximal double Roman domination in graphs
- Quadruple Roman domination in graphs
- Uncountably many minimal hereditary classes of graphs of unbounded clique-width
- Efficient computation of the oriented chromatic number of recursively defined digraphs
- Vertex coloring \((4K_1\), hole-twin, 5-wheel)-free graphs
- Identifying codes in the complementary prism of cycles
- Graph functionality
- Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs
- In)approximability of Maximum Minimal FVS
- Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
- Parameterized (approximate) defective coloring
- On width measures and topological problems on semi-complete digraphs
- Directed width parameters on semicomplete digraphs
- Parameterized (approximate) defective coloring
- Total Roman \(\{2\}\)-dominating functions in graphs
- A general framework for path convexities
- Branch-depth: generalizing tree-depth of graphs
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Parameterized Complexity of Graph Burning
- Parameterized complexity of graph burning
- 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
- Distance from triviality 2.0: hybrid parameterizations
- Linear-time algorithms for three domination-based separation problems in block graphs
- (In)approximability of maximum minimal FVS
- Meta-kernelization using well-structured modulators
- The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring
- Grammars and clique-width bounds from split decompositions
- On quasi-planar graphs: clique-width and logical description
- Acyclic polynomials of graphs
- A polynomial kernel for distance-hereditary vertex deletion
- Computing a metric basis of a bipartite distance-hereditary graph
- Clique-width of full bubble model graphs
- Treewidth versus clique number. I: Graph classes with a forbidden structure
- Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs
- \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
- More results on weighted independent domination
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)
