Searching for better fill-in
From MaRDI portal
Publication:2453556
DOI10.1016/j.jcss.2014.04.010zbMath1311.68077OpenAlexW2043976475WikidataQ60488407 ScholiaQ60488407MaRDI QIDQ2453556
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The parameterized complexity of local search for TSP, more refined
- Local search: is brute-force avoidable?
- Stable assignment with couples: parameterized complexity and local search
- The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
- Faster parameterized algorithms for \textsc{Minimum Fill-in}
- On rigid circuit graphs
- Minimal triangulations of graphs: a survey
- Searching the \(k\)-change neighborhood for TSP is W[1-hard]
- Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
- Counting clique trees and computing perfect elimination schemes in parallel
- Minimal vertex separators of chordal graphs
- Chordal completions of planar graphs
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Characterizations and algorithmic applications of chordal graph embeddings
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- A characterisation of rigid circuit graphs
- Parameterized complexity and local search approaches for the stable marriage problem with ties
- Incidence matrices and interval graphs
- Parametrized complexity theory.
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- On the Desirability of Acyclic Database Schemes
- On the hardness of losing weight
- The Use of Linear Graphs in Gauss Elimination
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Direct Methods for Sparse Linear Systems
- Computing the Minimum Fill-In is NP-Complete
- Algorithmic Aspects of Vertex Elimination on Graphs
- On the Complexity of Local Search for the Traveling Salesman Problem
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
- On Local Search and Placement of Meters in Networks
- Parameterized Complexity Results for Exact Bayesian Network Structure Learning
- Subexponential Parameterized Algorithm for Minimum Fill-In
- An Effective Heuristic Algorithm for the Traveling-Salesman Problem
