Graph Classes: A Survey
From MaRDI portal
Publication:4243764
DOI10.1137/1.9780898719796zbMATH Open0919.05001OpenAlexW1579049696MaRDI QIDQ4243764FDOQ4243764
Authors: Andreas Brandstädt, Van Bang Le, Jeremy P. Spinrad 
Publication date: 24 May 1999
Full work available at URL: https://doi.org/10.1137/1.9780898719796
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Structural characterization of families of graphs (05C75) Graph theory (05Cxx)
Cited In (only showing first 100 items - show all)
- A New Characterization of P 6-Free Graphs
- Spanning trees in random series-parallel graphs
- Induced subgraphs of graphs with large chromatic number. I. Odd holes
- Title not available (Why is that?)
- Clique-width of path powers
- On equistable, split, CIS, and related classes of graphs
- On the rainbow connectivity of graphs: complexity and FPT algorithms
- On graphs associated to sets of rankings
- Satisfiability of acyclic and almost acyclic CNF formulas
- Graphs of linear clique-width at most 3
- An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
- Enumerating minimal connected dominating sets in graphs of bounded chordality
- A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs
- Geodetic and Steiner geodetic sets in 3-Steiner distance hereditary graphs
- Two minimal forbidden subgraphs for double competition graphs of posets of dimension at most two
- Minimal dominating sets in graph classes: combinatorial bounds and enumeration
- Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
- Dimension-2 poset competition numbers and dimension-2 poset double competition numbers
- Minimal dominating sets in graph classes: combinatorial bounds and enumeration
- (Nearly-)tight bounds on the contiguity and linearity of cographs
- Subgraph isomorphism in graph classes
- On the number of minimal dominating sets on some graph classes
- Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs
- Isomorphism of weighted trees and Stanley's isomorphism conjecture for caterpillars
- The chromatic number of a signed graph
- Acyclic and star colorings of cographs
- Structural similarity of directed universal hierarchical graphs: a low computational complexity approach
- Computing role assignments of proper interval graphs in polynomial time
- Enumerating minimal dominating sets in chordal graphs
- Fast exact algorithm for \(L(2,1)\)-labeling of graphs
- Vertex-decomposable graphs, codismantlability, Cohen-Macaulayness, and Castelnuovo-Mumford regularity
- Win-win kernelization for degree sequence completion problems
- Clique cycle-transversals in distance-hereditary graphs
- Weighted independent sets in classes of \(P_6\)-free graphs
- Circular convex bipartite graphs: feedback vertex sets
- Maximum weight independent sets in classes related to claw-free graphs
- Color-bounded hypergraphs. VI: Structural and functional jumps in complexity
- On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem
- Feedback vertex sets on restricted bipartite graphs
- Enumerating minimal dominating sets in chordal bipartite graphs
- Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs
- Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
- Efficient algorithms for Roman domination on some classes of graphs
- Some remarks on the geodetic number of a graph
- Tractabilities and intractabilities on geometric intersection graphs
- On the generation of circuits and minimal forbidden sets
- On computing longest paths in small graph classes
- On the domination search number
- Linear-time algorithm for the paired-domination problem in convex bipartite graphs
- The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
- Complexity classification of some edge modification problems
- On algorithms for (\(P_5\), gem)-free graphs
- Finding large degree-anonymous subgraphs is hard
- Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
- Subexponential parameterized algorithms and kernelization on almost chordal graphs
- An improved algorithm for the longest induced path problem on \(k\)-chordal graphs
- Tree spanners on chordal graphs: complexity and algorithms
- Integration of topological measures for eliminating non-specific interactions in protein interaction networks
- The clique-separator graph for chordal graphs
- On 3-Steiner simplicial orderings
- Star coloring of certain graph classes
- A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs
- Equistable graphs, general partition graphs, triangle graphs, and graph products
- On the complexity of the independent set problem in triangle graphs
- Recognizing Helly edge-path-tree graphs and their clique graphs
- Computing a minimum outer-connected dominating set for the class of chordal graphs
- Subset feedback vertex set on graphs of bounded independent set size
- Hyperbolic bridged graphs
- On the convexity number of graphs
- Computing square roots of trivially perfect and threshold graphs
- Equistable simplicial, very well-covered, and line graphs
- The maximum vertex coverage problem on bipartite graphs
- Finding a minimum path cover of a distance-hereditary graph in polynomial time
- On the 2-rainbow domination in graphs
- Induced matchings in asteroidal triple-free graphs
- 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.
- Equistable distance-hereditary graphs
- Linear layouts measuring neighbourhoods in graphs
- Rebuilding convex sets in graphs
- Steiner distance and convexity in graphs
- Integrally normalizable matrices and zero-nonzero patterns
- Measuring instance difficulty for combinatorial optimization problems
- Tree decompositions with small cost
- Minimum feedback vertex set and acyclic coloring.
- Enumeration and maximum number of minimal dominating sets for chordal graphs
- Information theoretic measures of UHG graphs with low computational complexity
- Representing graphs as the intersection of cographs and threshold graphs
- A note on the complexity of locating-total domination in graphs
- A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
- The complexity of modular decomposition of Boolean functions
- Large Induced Subgraphs via Triangulations and CMSO
- \([1,2]\)-sets in graphs
- Elimination schemes and lattices
- Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
- On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
- Boxicity and treewidth
- Distance-hereditary graphs are clique-perfect
- Vertex decomposable graphs and obstructions to shellability
- Characterizing directed path graphs by forbidden asteroids
This page was built for publication: Graph Classes: A Survey
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4243764)
