Algorithmic Aspects of Vertex Elimination on Graphs

Cited in

(only showing first 100 items - show all)

Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
Maximum induced matchings for chordal graphs in linear time
On a property of minimal triangulations
Laminar structure of ptolemaic graphs with applications
Exploiting special structure in semidefinite programming: a survey of theory and applications
On 3-Steiner simplicial orderings
Decomposition by clique separators
\(K_ i\)-covers. I: Complexity and polytopes
Row-ordering schemes for sparse Givens transformations. II. Implicit graph model
Neighborhood perfect graphs
Efficient solutions of hierarchical systems of linear equations
A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring
The analysis of a nested dissection algorithm
Chordal graph recognition is in NC
The maximum k-colorable subgraph problem for chordal graphs
Sparse linear problems and the least squares method
A parallel graph partitioning algorithm for a message-passing multiprocessor
Algorithmique et calculs de complexité pour un solveur de type dissections emboîtées. (Algorithmic study and complexity bounds for a nested dissection solver)
Maximal chordal subgraphs
Weak bipolarizable graphs
Labeling algorithms for domination problems in sun-free chordal graphs
Algorithmic aspects of intersection graphs and representation hypergraphs
A note on odd/even cycles
On symbolic factorization of partitioned sparse symmetric matrices
On minimal augmentation of a graph to obtain an interval graph
Optimal packing and covering in the plane are NP-complete
Independent domination in chordal graphs
Inheritance principles for chordal graphs
Some aspects of the semi-perfect elimination
\((i,j)\) competition graphs
Cycle-free partial orders and chordal comparability graphs
Finding large holes
An inertia formula for Hermitian matrices with sparse inverses
Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
Representing triangulated graphs in stars
A chordal preconditioner for large-scale optimization
An optimal algorithm for solving the searchlight guarding problem on weighted interval graphs
Minimal vertex separators of chordal graphs
On the consecutive ones property
Construction of a simple elimination scheme for a chordal comparability graph in linear time
The forbidden subgraph characterization of directed vertex graphs
Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs
On constructing the elimination tree
On cocolourings and cochromatic numbers of graphs
The maximum clique problem
Recognition algorithm for intersection graphs of edge disjoint paths in a tree
Arboricity and bipartite subgraph listing algorithms
Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph
New linear time algorithms for generating perfect elimination orderings of chordal graphs
Fixed-parameter tractability of graph modification problems for hereditary properties
\(r\)-dominating cliques in graphs with hypertree structure
Separators and structure prediction in sparse orthogonal factorization
LexBFS-orderings and powers of chordal graphs
Cuts, matrix completions and graph rigidity
The algorithmic use of hypertree structure and maximum neighbourhood orderings
On treewidth and minimum fill-in of asteroidal triple-free graphs
Separability generalizes Dirac's theorem
On linear and circular structure of (claw, net)-free graphs
Interval degree and bandwidth of a graph
Maximum independent set and maximum clique algorithms for overlap graphs
Matrix completions and chordal graphs
Hereditary dominating pair graphs
Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
A practical algorithm for making filled graphs minimal
On vertex ranking of a starlike graph
An implementation of the iterative proportional fitting procedure by propagation trees.
Perfect edge domination and efficient edge domination in graphs
On claw-free asteroidal triple-free graphs
Restricted triangulation on circulant graphs
Decomposition in multidimensional Boolean-optimization problems with sparse matrices
Method of fundamental solutions for 3D elasticity with body forces by coupling compactly supported radial basis functions
Graph extremities defined by search algorithms
An introduction to clique minimal separator decomposition
Computing a clique tree with the algorithm maximal label search
The normal graph conjecture for two classes of sparse graphs
Solving problems on graphs of high rank-width
An \(O(n^2)\) time algorithm for the minimal permutation completion problem
Tractability of most probable explanations in multidimensional Bayesian network classifiers
A simple linear time algorithm for the locally connected spanning tree problem on maximal planar chordal graphs
On the classes of interval graphs of limited nesting and count of lengths
On distance-preserving elimination orderings in graphs: complexity and algorithms
Non-edge orientation and vertex ordering characterizations of some classes of bigraphs
Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
Tree decompositions with small cost
On the structure of (\(P_{5}\),\,gem)-free graphs
Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
Paired threshold graphs
A characterization of graphs with interval two-step graphs
Chromatic numbers of competition graphs
Recognition of some perfectly orderable graph classes
On the semi-perfect elimination
A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
Recognition of perfect elimination bipartite graphs
Parallel computation of perfect elimination schemes using partition techniques on triangulated graphs
Generating and characterizing the perfect elimination orderings of a chordal graph
A polynomial algorithm for the parity path problem on perfectly orientable graphs
Quasi-threshold graphs
Finding a sun in building-free graphs
Computation of the Shapley value of minimum cost spanning tree games: P-hardness and polynomial cases

This page was built for publication: Algorithmic Aspects of Vertex Elimination on Graphs

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