scientific article; zbMATH DE number 2044928

Egon Wanke, Frank Gurski, W. Espelage

Publication date: 18 February 2004

Full work available at URL: http://link.springer.de/link/service/series/0558/bibs/2204/22040117.htm

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

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)

Related Items (59)

Characterizations for co-graphs defined by restricted NLC-width or clique-width operations ⋮ Acyclic coloring parameterized by directed clique-width ⋮ Unnamed Item ⋮ Minimum maximal matchings in cubic graphs ⋮ Polynomial algorithms for protein similarity search for restricted mRNA structures ⋮ On powers of graphs of bounded NLC-width (clique-width) ⋮ Vertex-minors, monadic second-order logic, and a conjecture by Seese ⋮ Characterizations for restricted graphs of NLC-width 2 ⋮ Colouring diamond-free graphs ⋮ Colouring square-free graphs without long induced paths. ⋮ MSOL partitioning problems on graphs of bounded treewidth and clique-width ⋮ Parameterized edge Hamiltonicity ⋮ Bounding the Clique-Width of H-free Chordal Graphs ⋮ Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ Fair allocation algorithms for indivisible items under structured conflict constraints ⋮ Clique‐width: Harnessing the power of atoms ⋮ On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract) ⋮ Graphs of separability at most 2 ⋮ Polynomial-time recognition of clique-width \(\leq 3\) graphs ⋮ Stability, vertex stability, and unfrozenness for special graph classes ⋮ On switching classes, NLC-width, cliquewidth and treewidth ⋮ Clique-Width for Graph Classes Closed under Complementation ⋮ Directed NLC-width ⋮ Obstructions for linear rank-width at most 1 ⋮ Covering a Graph with Clubs ⋮ Finding a minimum path cover of a distance-hereditary graph in polynomial time ⋮ Graphs of Separability at Most Two: Structural Characterizations and Their Consequences ⋮ Line graphs of bounded clique-width ⋮ On the parameterized complexity of computing balanced partitions in graphs ⋮ Efficient computation of the oriented chromatic number of recursively defined digraphs ⋮ Solving some NP-complete problems using split decomposition ⋮ The behavior of clique-width under graph operations and graph transformations ⋮ Oriented coloring on recursively defined digraphs ⋮ Recent developments on graphs of bounded clique-width ⋮ \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth ⋮ On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width ⋮ Approximating clique-width and branch-width ⋮ On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth ⋮ Vertex disjoint paths on clique-width bounded graphs ⋮ Well-quasi-ordering versus clique-width: new results on bigenic classes ⋮ Clique-width and well-quasi-ordering of triangle-free graph classes ⋮ An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width ⋮ Unnamed Item ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes ⋮ Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width ⋮ Comparing linear width parameters for directed graphs ⋮ Colouring square-free graphs without long induced paths ⋮ Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs ⋮ Computing maximum stable sets for distance-hereditary graphs ⋮ Digraphs of Bounded Width ⋮ Unnamed Item ⋮ Optimal centrality computations within bounded clique-width graphs ⋮ Maximum matching in almost linear time on graphs of bounded clique-width ⋮ On the relationship between NLC-width and linear NLC-width ⋮ Tree Pivot-Minors and Linear Rank-Width ⋮ Knocking out \(P_k\)-free graphs ⋮ Canonisation and Definability for Graphs of Bounded Rank Width ⋮ On algorithms for (\(P_5\), gem)-free graphs

This page was built for publication: