Linear-time certifying recognition algorithms and forbidden induced subgraphs
From MaRDI portal
(Redirected from Publication:5503435)
Recommendations
- scientific article; zbMATH DE number 2079335
- Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
- Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
- A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements
- A linear-time certifying algorithm for recognizing generalized series-parallel graphs
Cited in
(64)- The k-hop connected dominating set problem: approximation and hardness
- A graph theoretic approach to solve special knapsack problems in polynomial time
- Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs
- Acyclic Matching in Some Subclasses of Graphs
- Transitivity on subclasses of chordal graphs
- Transitivity on subclasses of bipartite graphs
- Letter graphs and geometric grid classes of permutations: characterization and recognition
- Algorithmic study of \(d_2\)-transitivity of graphs
- Complexity of total dominator coloring in graphs
- Finding a potential community in networks
- Counting and enumerating independent sets with applications to combinatorial optimization problems
- Double dominating sequences in bipartite and co-bipartite graphs
- Finding a chain graph in a bipartite permutation graph
- Edge deletion problems: branching facilitated by modular decomposition
- Edge contractions in subclasses of chordal graphs
- Subgraph isomorphism in graph classes
- Approximability of the path-distance-width for AT-free graphs
- Graph classes and forbidden patterns on three vertices
- Positional dominance: concepts and algorithms
- An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
- Some new considerations about double nested graphs
- Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs
- Computation of Grundy dominating sequences in (co-)bipartite graphs
- Role coloring bipartite graphs
- Characterization and recognition of Radon-independent sets in split graphs
- Recognition of split-graphic sequences
- Solving matching problems efficiently in bipartite graphs
- Approximating the path-distance-width for AT-free graphs and graphs in related classes
- Verifying the product of generalized Boolean matrix multiplication and its applications to detect small subgraphs
- Algorithmic study on 2-transitivity of graphs
- Cosecure domination: hardness results and algorithms
- The complexity of the defensive domination problem in special graph classes
- Some new algorithmic results on co-secure domination in graphs
- Certifying induced subgraphs in large graphs
- Competitive diffusion on weighted graphs
- Acyclic matching in some subclasses of graphs
- Algorithms and hardness results for edge total domination problem in graphs
- Grundy double domination number: bounds, graph operations, and efficient computation for P₄-tidy graphs
- Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
- Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection
- Ferrers dimension of grid intersection graphs
- Betti numbers and anti-lecture Hall compositions of random threshold graphs
- Certifying algorithms
- A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements
- On a Verification Framework for Certifying Distributed Algorithms: Distributed Checking and Consistency
- Ideally connected cographs and chordal graphs
- Kernels for the disjoint paths problem on subclasses of chordal graphs
- Fast diameter computation within split graphs
- On complementarily transitivity of graphs
- A simple certifying algorithm for 3-edge-connectivity
- On the complexity of finding a potential community
- The maximum cardinality cut problem in co-bipartite chain graphs
- Certifying induced subgraphs in large graphs
- Transitivity in some graph-classes
- A simple linear-time recognition algorithm for weakly quasi-threshold graphs
- A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
- On minimal forbidden subgraph characterizations of balanced graphs
- On the complexity of minimum maximal uniquely restricted matching
- Strict chordal and strict split digraphs
- Cover-incomparability graphs and chordal graphs
- Computational aspects of double dominating sequences in graphs
- Algorithms for maximum internal spanning tree problem for some graph classes
- Edge contractions in subclasses of chordal graphs
- \(1\)-perfectly orientable graphs and graph products
This page was built for publication: Linear-time certifying recognition algorithms and forbidden induced subgraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5503435)
