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) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05)

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

• 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?)
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• A characterisation of rigid circuit graphs
• 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
• 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 Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs
• Parameterized coloring problems on 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)

• scientific article; zbMATH DE number 5050599 (Why is no real title available?)
• On listing, sampling, and counting the chordal graphs with edge constraints
• Generating Random Hyperbolic Graphs in Subquadratic Time
• Generating Practical Random Hyperbolic Graphs in Near-Linear Time and with Sub-Linear Memory
• 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
• On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
• A separator-based method for generating weakly chordal graphs
• Systematic generation of linear graphs - check and extension of the list of Uhlenbeck and Ford
• Listing Chordal Graphs and Interval Graphs
• Cograph generation with linear delay
• Two methods for the generation of chordal graphs
• Generation of random chordal graphs using subtrees of a tree

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)