Linear-time generation of random chordal graphs

DOI10.1007/978-3-319-57586-5_37MaRDI QIDQ5283388zbMATH OpenOpenAlexFDO

Authors Oylum Şeker, Pinar Heggernes, Tınaz Ekim, Z. Caner Taşkın

Publication date 21 July 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-57586-5_37

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Analysis of algorithms (68W40)

Recommendations

• Generation of random chordal graphs using subtrees of a tree
• An efficient representation of chordal graphs
• The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation
• Algorithms for generating strongly chordal graphs
• Two methods for the generation of chordal graphs

Cites work

• A characterisation of rigid circuit graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithmic graph theory and perfect graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Approximating interval coloring and max-coloring in chordal graphs
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• Enumerating minimal dominating sets in chordal graphs
• Experimental and Efficient Algorithms
• Graph Classes: A Survey
• scientific article; zbMATH DE number 3152801 (Why is no real title available?)
• scientific article; zbMATH DE number 48812 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 3420184 (Why is no real title available?)
• Incidence matrices and interval graphs
• Minimal triangulations of graphs: a survey
• On Generating Random Network Structures: Trees
• On rigid circuit graphs
• Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs
• Parameterized coloring problems on chordal graphs
• Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs
• Subset feedback vertex sets in chordal graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Two methods for the generation of chordal graphs

Cited in

(14)

• Cograph generation with linear delay
• The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation
• An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs
• Algorithms for generating strongly chordal graphs
• Generating Random Hyperbolic Graphs in Subquadratic Time
• On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
• Listing Chordal Graphs and Interval Graphs
• Generating Practical Random Hyperbolic Graphs in Near-Linear Time and with Sub-Linear Memory
• Generation of random chordal graphs using subtrees of a tree
• scientific article; zbMATH DE number 5050599 (Why is no real title available?)
• A separator-based method for generating weakly chordal graphs
• Systematic generation of linear graphs - check and extension of the list of Uhlenbeck and Ford
• Two methods for the generation of chordal graphs
• On listing, sampling, and counting the chordal graphs with edge constraints

This page was built for publication: Linear-time generation of random chordal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5283388)