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
The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs, Linear-Time Generation of Random Chordal Graphs, Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs, Minimal elimination of planar graphs, What Is between Chordal and Weakly Chordal Graphs?, Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number, An efficient algorithm for counting Markov equivalent DAGs, Beyond Helly graphs: the diameter problem on absolute retracts, Minimum Average Distance Clique Trees, Approximation and Kernelization for Chordal Vertex Deletion, A Class of Balanced Matrices Arising from Location Problems, Independent set under a change constraint from an initial solution, Clique trees of chordal graphs: leafage and 3-asteroidals, A story of diameter, radius, and (almost) Helly property, Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs, Chordal graphs and their clique graphs, A Characterisation of the Minimal Triangulations of Permutation Graphs, Exact algorithms for restricted subset feedback vertex set in chordal and split graphs, Dually chordal graphs, Treewidth versus clique number. II: Tree-independence number, On domination elimination orderings and domination graphs, Algorithms and complexity of sandwich problems in graphs (extended abstract), On the structure of (pan, even hole)‐free graphs, Mathematical approaches to comparative linguistics, Unique Perfect Phylogeny Is NP-Hard, Recognizing Proper Tree-Graphs, The algorithmic use of hypertree structure and maximum neighbourhood orderings, Restricted unimodular chordal graphs, Intersection graphs of non-crossing paths, Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage, Maximal sub-triangulation in pre-processing phylogenetic data, Diameter determination on restricted graph families, Unnamed Item, Minimal elimination ordering for graphs of bounded degree, Minimizing phylogenetic number to find good evolutionary trees, Two strikes against perfect phylogeny, Junction trees of general graphs, Unnamed Item, An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs, On some simplicial elimination schemes for chordal graphs, Unnamed Item, Identifying phylogenetic trees, Defining a Phylogenetic Tree with the Minimum Number of $r$-State Characters, Efficient parallel algorithm to compute a doubly perfect elimination ordering of a doubly chordal graph, Unnamed Item, Polynomially bounded algorithms for locatingp-centers on a tree, 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
