Finding optimal triangulations parameterized by edge clique cover

DOI10.1007/s00453-022-00932-0OpenAlexW3043685179MaRDI QIDQ2161006

Tuukka Korhonen

Publication date: 3 August 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1912.10989

zbMATH Keywords

treewidthparameterized algorithmspotential maximal cliquesedge clique coverminimum fill-infractional hypertreewidth

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Uses Software

• CPLEX
• bnlearn
• Algorithm 457
• HyperBench

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Treewidth and pathwidth parameterized by the vertex cover number
• Computing hypergraph width measures exactly
• Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph
• Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques
• On the complexity of computing treelength
• Listing all potential maximal cliques of a graph
• Algorithms parameterized by vertex cover and modular width, through potential maximal cliques
• On the tractability of optimization problems on \(H\)-graphs
• Positive-instance driven dynamic programming for treewidth
• A revisit of the scheme for computing treewidth and minimum fill-in
• Identifying phylogenetic trees
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• Large Induced Subgraphs via Triangulations and CMSO
• Bayesian Networks and Decision Graphs
• Generalized hypertree decompositions: NP-hardness and tractable variants
• Known Algorithms for Edge Clique Cover are Probably Optimal
• Fourier meets M\"{o}bius: fast subset convolution
• A Parameterized Algorithm for Chordal Sandwich
• Constraint solving via fractional edge covers
• Exact Algorithms for Treewidth and Minimum Fill-In
• A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies
• Solving Graph Problems via Potential Maximal Cliques
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
• Minimal Triangulation Algorithms for Perfect Phylogeny Problems
• Algorithm 457: finding all cliques of an undirected graph

This page was built for publication: Finding optimal triangulations parameterized by edge clique cover