scientific article; zbMATH DE number 2044928
From MaRDI portal
Publication:4448752
zbMATH Open1042.68626MaRDI QIDQ4448752FDOQ4448752
Authors: W. Espelage, Frank Gurski, Egon Wanke 
Publication date: 18 February 2004
Full work available at URL: http://link.springer.de/link/service/series/0558/bibs/2204/22040117.htm
Title of this publication is not available (Why is that?)
Recommendations
- Computing Graph Polynomials on Graphs of Bounded Clique-Width
- scientific article; zbMATH DE number 1262783
- Linear time solvable optimization problems on graphs of bounded clique-width
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- scientific article; zbMATH DE number 6850484
- Clique-width is NP-complete
- Algorithmic lower bounds for problems parameterized by clique-width
- On graphs with polynomially solvable maximum-weight clique problem
- Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract)
- Clique-width minimization is NP-hard
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (68)
- Clique-width and well-quasi-ordering of triangle-free graph classes
- Stability, vertex stability, and unfrozenness for special graph classes
- Clique‐width: Harnessing the power of atoms
- \(b\)-coloring parameterized by clique-width
- Fair allocation algorithms for indivisible items under structured conflict constraints
- Succinct data structures for bounded clique-width graphs
- Title not available (Why is that?)
- On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract)
- Directed NLC-width
- Tree pivot-minors and linear rank-width
- Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
- Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
- Acyclic coloring parameterized by directed clique-width
- Colouring square-free graphs without long induced paths
- Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width
- Graphs of separability at most 2
- Polynomial-time recognition of clique-width \(\leq 3\) graphs
- On switching classes, NLC-width, cliquewidth and treewidth
- Minimum maximal matchings in cubic graphs
- Title not available (Why is that?)
- Clique-width minimization is NP-hard
- Vertex disjoint paths on clique-width bounded graphs
- \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth
- Recent developments on graphs of bounded clique-width
- Efficient computation of the oriented chromatic number of recursively defined digraphs
- On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- Parameterized edge Hamiltonicity
- Computing Graph Polynomials on Graphs of Bounded Clique-Width
- Well-quasi-ordering versus clique-width: new results on bigenic classes
- Covering a graph with clubs
- Well-quasi-ordering versus clique-width: new results on bigenic classes
- Oriented coloring on recursively defined digraphs
- Knocking out \(P_k\)-free graphs
- Vertex-minors, monadic second-order logic, and a conjecture by Seese
- On powers of graphs of bounded NLC-width (clique-width)
- Clique-width is NP-complete
- Comparing linear width parameters for directed graphs
- Colouring square-free graphs without long induced paths
- Colouring diamond-free graphs
- On algorithms for (\(P_5\), gem)-free graphs
- MSOL partitioning problems on graphs of bounded treewidth and clique-width
- Graphs of separability at most two: structural characterizations and their consequences
- Solving some NP-complete problems using split decomposition
- Line graphs of bounded clique-width
- Characterizations for restricted graphs of NLC-width 2
- Maximum matching in almost linear time on graphs of bounded clique-width
- Finding a minimum path cover of a distance-hereditary graph in polynomial time
- Clique-width for graph classes closed under complementation
- Approximating clique-width and branch-width
- Canonisation and Definability for Graphs of Bounded Rank Width
- On the relationship between NLC-width and linear NLC-width
- On \textsf{NC} algorithms for problems on bounded rank-width graphs
- On the parameterized complexity of computing balanced partitions in graphs
- Clique-width of graph classes defined by two forbidden induced subgraphs
- Query efficient implementation of graphs of bounded clique-width
- Title not available (Why is that?)
- Bounding the clique-width of \(H\)-free chordal graphs
- Digraphs of bounded 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
- An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width
- Computing maximum stable sets for distance-hereditary graphs
- Polynomial algorithms for protein similarity search for restricted mRNA structures
- Optimal centrality computations within bounded clique-width graphs
- A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4448752)
