Searching for better fill-in

DOI10.1016/J.JCSS.2014.04.010MaRDI QIDQ2453556zbMATH OpenOpenAlexWikidataFDO

Authors Fedor V. Fomin, Yngve Villanger

Publication date 10 June 2014

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2014.04.010

zbMATH Keywords

chordal graphlocal searchminimum fill-inparameterized complexitytriangulation

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Searching for better fill-in
• Filling gaps in space filling
• Filling the nest gaps
• In search of the best approximant
• Improving best-reply search
• scientific article; zbMATH DE number 1304976
• Searching for searchers

Cites work

• A characterisation of rigid circuit graphs
• A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
• Algorithmic Aspects of Vertex Elimination on Graphs
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Characterizations and algorithmic applications of chordal graph embeddings
• Chordal completions of planar graphs
• Computing the Minimum Fill-In is NP-Complete
• Counting clique trees and computing perfect elimination schemes in parallel
• Direct Methods for Sparse Linear Systems
• Faster parameterized algorithms for \textsc{Minimum Fill-in}
• Fixed-parameter tractability of graph modification problems for hereditary properties
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 554763 (Why is no real title available?)
• scientific article; zbMATH DE number 1082099 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1927376 (Why is no real title available?)
• scientific article; zbMATH DE number 4121482 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 3420184 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• scientific article; zbMATH DE number 4184603 (Why is no real title available?)
• Incidence matrices and interval graphs
• Local search: is brute-force avoidable?
• Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
• Minimal triangulations of graphs: a survey
• Minimal vertex separators of chordal graphs
• On Local Search and Placement of Meters in Networks
• On rigid circuit graphs
• On the Complexity of Local Search for the Traveling Salesman Problem
• On the Desirability of Acyclic Database Schemes
• On the hardness of losing weight
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• Parameterized complexity and local search approaches for the stable marriage problem with ties
• Parameterized complexity results for exact Bayesian network structure learning
• Parametrized complexity theory.
• Searching the \(k\)-change neighborhood for TSP is W[1]-hard
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Stable assignment with couples: parameterized complexity and local search
• Subexponential parameterized algorithm for minimum fill-in
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
• The parameterized complexity of local search for TSP, more refined
• The Use of Linear Graphs in Gauss Elimination
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs

Cited in

(2)

• A revisit of the scheme for computing treewidth and minimum fill-in
• Searching for better fill-in

Describes a project that uses

Uses Software

• CSparse

This page was built for publication: Searching for better fill-in

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