Algorithms for Generating Strongly Chordal Graphs
| Autor: | Asish Mukhopadhyay, Md. Zamilur Rahman |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Class (set theory)
Mathematics::Combinatorics Mathematics::Commutative Algebra Mathematics::Complex Variables Computer Science::Discrete Mathematics Computer science Chordal graph Graph algorithms Graph generation Characterization (mathematics) Computer Science::Data Structures and Algorithms Algorithm MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Transactions on Computational Science XXXVIII ISBN: 9783662631690 |
| Popis: | Graph generation serves many useful purposes: cataloguing, testing conjectures, to which we would like to add that of producing test instances for graph algorithms. Strongly chordal graphs are a subclass of chordal graphs for which polynomial-time algorithms could be designed for problems which are NP-complete for the parent class of chordal graphs. In this paper, we propose three different algorithms for generating strongly chordal graphs, each based on a different characterization of strongly chordal graphs. Each one of them is interesting in its own right, but the third one has turned out to be the most versatile in the sense that it can generate strongly chordal graphs with multiple components and does not require a chordal graph as input. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|