scientific article; zbMATH DE number 1512682
From MaRDI portal
Publication:4508369
zbMath0961.05062MaRDI QIDQ4508369
Jean-Marc Lanlignel, Bruce A. Reed, Michel A. Habib, Udi Rotics, Derek Gordon Corneil
Publication date: 13 May 2001
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (37)
The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions. ⋮ Algorithms for vertex-partitioning problems on graphs with fixed clique-width. ⋮ Polynomial algorithms for protein similarity search for restricted mRNA structures ⋮ Vertex-minors, monadic second-order logic, and a conjecture by Seese ⋮ The rank-width of edge-coloured graphs ⋮ Inductive computations on graphs defined by clique-width expressions ⋮ Algorithmic uses of the Feferman-Vaught theorem ⋮ Graphs of Linear Clique-Width at Most 3 ⋮ Tree-width and the monadic quantifier hierarchy. ⋮ Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs ⋮ Polynomial-time recognition of clique-width \(\leq 3\) graphs ⋮ Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs ⋮ New plain-exponential time classes for graph homomorphism ⋮ Distance labeling scheme and split decomposition ⋮ Well-quasi-ordering of matrices under Schur complement and applications to directed graphs ⋮ The complexity of finding uniform sparsest cuts in various graph classes ⋮ Dynamic Distance Hereditary Graphs Using Split Decomposition ⋮ Vertex-minor reductions can simulate edge contractions ⋮ Line graphs of bounded clique-width ⋮ Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width ⋮ Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width ⋮ Counting truth assignments of formulas of bounded tree-width or clique-width ⋮ On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic ⋮ Graph Operations, Graph Transformations and Monadic Second-Order Logic: ⋮ Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width ⋮ On a disparity between relative cliquewidth and relative NLC-width ⋮ Approximating clique-width and branch-width ⋮ Graphs of linear clique-width at most 3 ⋮ Vertex disjoint paths on clique-width bounded graphs ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ New Plain-Exponential Time Classes for Graph Homomorphism ⋮ Graph operations characterizing rank-width ⋮ Rank-width and vertex-minors ⋮ The recognizability of sets of graphs is a robust property ⋮ Optimal centrality computations within bounded clique-width graphs ⋮ On the relationship between NLC-width and linear NLC-width ⋮ Edge dominating set and colorings on graphs with fixed clique-width
This page was built for publication:
