Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs

DOI10.1137/0214020zbMath0562.68055OpenAlexW4252143234WikidataQ61687612 ScholiaQ61687612MaRDI QIDQ3675541

Mihalis Yannakakis, Robert Endre Tarjan

Publication date: 1985

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0214020

zbMATH Keywords

nonchordal graph unchorded cycle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Related Items (22)

An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph ⋮ BOUNDED SEARCH TREE ALGORITHMS FOR PARAMETRIZED COGRAPH DELETION: EFFICIENT BRANCHING RULES BY EXPLOITING STRUCTURES OF SPECIAL GRAPH CLASSES ⋮ Fixed-parameter tractability of graph modification problems for hereditary properties ⋮ Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs ⋮ Exact algorithms and applications for tree-like Weighted Set Cover ⋮ Graph searches and their end vertices ⋮ The parallel complexity of elimination ordering procedures ⋮ Inferring multivalued dependencies from functional and join dependencies ⋮ Certifying algorithms ⋮ End vertices of graph searches on bipartite graphs ⋮ Strict chordal and strict split digraphs ⋮ Polarity of chordal graphs ⋮ Two fixed-parameter algorithms for vertex covering by paths on trees ⋮ Edge deletion problems: branching facilitated by modular decomposition ⋮ Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs ⋮ On split-coloring problems ⋮ Paired threshold graphs ⋮ Unnamed Item ⋮ Parallel computation of perfect elimination schemes using partition techniques on triangulated graphs ⋮ Tree decompositions and social graphs ⋮ A faster algorithm to recognize even-hole-free graphs ⋮ Unnamed Item

This page was built for publication: Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs