A characterisation of rigid circuit graphs
From MaRDI portal
Publication:1846437
DOI10.1016/0012-365X(74)90002-8zbMath0288.05128MaRDI QIDQ1846437
Publication date: 1974
Published in: Discrete Mathematics (Search for Journal in Brave)
Related Items (only showing first 100 items - show all)
Combining polynomial running time and fast convergence for the disk-covering method. ⋮ Perfect edge domination and efficient edge domination in graphs ⋮ Minimal triangulations of graphs: a survey ⋮ A vertex incremental approach for maintaining chordality ⋮ Intersection graphs of paths in a tree ⋮ Characterizing intersection classes of graphs ⋮ Graph minors. V. Excluding a planar graph ⋮ Neighborhood perfect graphs ⋮ The parallel solution of domination problems on chordal and strongly chordal graphs ⋮ Rank inequalities for chordal graphs ⋮ A faster algorithm to recognize undirected path graphs ⋮ Generating and characterizing the perfect elimination orderings of a chordal graph ⋮ Tolerance intersection graphs of degree bounded subtrees of a tree with constant tolerance 2 ⋮ Clique tree generalization and new subclasses of chordal graphs ⋮ New linear time algorithms for generating perfect elimination orderings of chordal graphs ⋮ Tree-decompositions, tree-representability and chordal graphs ⋮ Intersection graphs of vertex disjoint paths in a tree ⋮ Treewidth computation and extremal combinatorics ⋮ Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs ⋮ Simplicial decompositions of graphs: A survey of applications ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Algorithmic aspects of intersection graphs and representation hypergraphs ⋮ Tree representations of graphs ⋮ A note on \(r\)-dominating cliques ⋮ Unit hypercube visibility numbers of trees ⋮ The algorithmic use of hypertree structure and maximum neighbourhood orderings ⋮ The lexicographic product of some chordal graphs and of cographs preserves \(b\)-continuity ⋮ Two characterisations of the minimal triangulations of permutation graphs ⋮ Chordal digraphs ⋮ Matching and multidimensional matching in chordal and strongly chordal graphs ⋮ Finding intersection models: from chordal to Helly circular-arc graphs ⋮ Reduced clique graphs of chordal graphs ⋮ Graph triangulations and the compatibility of unrooted phylogenetic trees ⋮ Characterization and representation problems for intersection betweennesses ⋮ Subgraph trees in graph theory ⋮ Chordal graphs in triangular decomposition in top-down style ⋮ The vertex leafage of chordal graphs ⋮ Computing a minimum outer-connected dominating set for the class of chordal graphs ⋮ Moplex orderings generated by the LexDFs algorithm ⋮ Faster parameterized algorithms for \textsc{Minimum Fill-in} ⋮ Recovering trees from well-separated multi-state characters. ⋮ On asteroidal sets in chordal graphs ⋮ Characterization of classical graph classes by weighted clique graphs ⋮ Locational analysis ⋮ An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ Intersection properties of graphs ⋮ Some aspects of the semi-perfect elimination ⋮ Searching for better fill-in ⋮ Intersection representations of matrices by subtrees and unicycles on graphs ⋮ Counting the number of independent sets in chordal graphs ⋮ Cycle-free partial orders and chordal comparability graphs ⋮ Peakless functions on graphs ⋮ The matroid structure of representative triple sets and triple-closure computation ⋮ Convex tree realizations of partitions ⋮ The \(k\)-edge intersection graphs of paths in a tree ⋮ On compatibility and incompatibility of collections of unrooted phylogenetic trees ⋮ Representing edge intersection graphs of paths on degree 4 trees ⋮ The complexity of reconstructing trees from qualitative characters and subtrees ⋮ Complexity of distance paired-domination problem in graphs ⋮ Tree decomposition and discrete optimization problems: a survey ⋮ Treewidth computations. I: Upper bounds ⋮ Separator orders in interval, cocomparability, and AT-free graphs ⋮ Tree reconstruction from multi-state characters ⋮ Strong branchwidth and local transversals ⋮ Constant tolerance intersection graphs of subtrees of a tree ⋮ On the complexity of computing treelength ⋮ Mixing of Markov chains for independent sets on chordal graphs with bounded separators ⋮ Exact leaf powers ⋮ Representation characterizations of chordal bipartite graphs ⋮ Information storage and retrieval - mathematical foundations. II: Combinatorial problems ⋮ A parallel algorithm for generating bicompatible elimination orderings of proper interval graphs ⋮ Dyadic representations of graphs ⋮ Fast compatibility testing for rooted phylogenetic trees ⋮ On compact and efficient routing in certain graph classes ⋮ A note on perfect Gaussian elimination ⋮ Trivially perfect graphs ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ Hypergraphes arbores ⋮ Equivalences and the complete hierarchy of intersection graphs of paths in a tree ⋮ Counting clique trees and computing perfect elimination schemes in parallel ⋮ Induced matchings ⋮ Extending cycles in graphs ⋮ Perfect elimination orderings of chordal powers of graphs ⋮ An optimal algorithm for solving the searchlight guarding problem on weighted interval graphs ⋮ Intersection models of weakly chordal graphs ⋮ The clique-separator graph for chordal graphs ⋮ The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs ⋮ Recognizing clique graphs of directed and rooted path graphs ⋮ Brambles and independent packings in chordal graphs ⋮ Multiplicity adjustment for temporal and spatial scan statistics using Markov property ⋮ The forbidden subgraph characterization of directed vertex graphs ⋮ Completeness for intersection classes ⋮ Some aspects of perfect elimination orderings in chordal graphs ⋮ On the representation of triangulation graphs in trees ⋮ NP-complete problems simplified on tree schemas ⋮ Interval graphs and related topics ⋮ On the pathwidth of chordal graphs ⋮ Linear-time algorithms for tree root problems ⋮ Recognition algorithm for intersection graphs of edge disjoint paths in a tree
Cites Work
This page was built for publication: A characterisation of rigid circuit graphs
