Avoidable vertices and edges in graphs: existence, characterization, and applications
From MaRDI portal
Publication:2065802
DOI10.1016/j.dam.2021.12.006zbMath1480.05039OpenAlexW4200082749MaRDI QIDQ2065802
Jesse Beisegel, Martin Milanič, Maria Chudnovsky, Mary Servatius, Vladimir A. Gurvich
Publication date: 13 January 2022
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2021.12.006
maximum weight clique problem1-perfectly orientable graphLBFSavoidable edgeavoidable vertexbisimplicial elimination ordering
Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Distance in graphs (05C12) Data structures (68P05)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A Dirac-type characterization of \(k\)-chordal graphs
- Approximation algorithms for intersection graphs
- \(1\)-perfectly orientable graphs and graph products
- On rigid circuit graphs
- Minimal triangulations of graphs: a survey
- Efficient bounds for the stable set, vertex cover and set packing problems
- An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs
- An algorithm for fraternal orientation of graphs
- Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
- In-tournament digraphs
- Characterizations and algorithmic applications of chordal graph embeddings
- Separability generalizes Dirac's theorem
- Efficient graph representations
- Linear-time recognition of circular-arc graphs
- Listing all potential maximal cliques of a graph
- Graph extremities defined by search algorithms
- House of Graphs: a database of interesting graphs
- On the semi-perfect elimination
- Dirac-type characterizations of graphs without long chordless cycles
- Maximum cardinality search for computing minimal triangulations of graphs
- Algorithmic graph theory and perfect graphs
- Treewidth versus clique number in graph classes with a forbidden structure
- Avoidable paths in graphs
- Avoidable vertices and edges in graphs
- Incidence matrices and interval graphs
- 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs
- On cyclically orientable graphs
- Vertex elimination orderings for hereditary graph classes
- Triangulated graphs and the elimination process
- Treewidth and Minimum Fill-in: Grouping the Minimal Separators
- Large Induced Subgraphs via Triangulations and CMSO
- Finding Induced Subgraphs via Minimal Triangulations
- Elimination graphs
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Extremities and orderings defined by generalized graph search algorithms
- Convexity in Graphs and Hypergraphs
- A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Perfect Elimination and Chordal Bipartite Graphs
- Graph Classes: A Survey
- AnO(m+nlogn) Algorithm for the Maximum-Clique Problem in Circular-Arc Graphs
- Generating weakly triangulated graphs
- Reducibility among Combinatorial Problems
- Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure
- Partial Characterizations of 1‐Perfectly Orientable Graphs
- CLUSTER ALGEBRAS OF FINITE TYPE AND POSITIVE SYMMETRIZABLE MATRICES
- Max flows in O(nm) time, or better
- Shifting paths to avoidable ones
