Avoidable vertices and edges in graphs: existence, characterization, and applications
DOI10.1016/J.DAM.2021.12.006zbMATH Open1480.05039OpenAlexW4200082749MaRDI QIDQ2065802FDOQ2065802
Authors: Jesse Beisegel, Maria Chudnovsky, Martin Milanič, Mary Servatius, Vladimir 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
Recommendations
maximum weight clique problem1-perfectly orientable graphLBFSavoidable edgeavoidable vertexbisimplicial elimination ordering
Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Distance in graphs (05C12) Paths and cycles (05C38)
Cites Work
- House of Graphs: a database of interesting graphs
- Reducibility among combinatorial problems
- Graph Classes: A Survey
- Efficient graph representations
- Linear-time recognition of circular-arc graphs
- Dirac-type characterizations of graphs without long chordless cycles
- Algorithmic graph theory and perfect graphs
- Incidence matrices and interval graphs
- Convexity in Graphs and Hypergraphs
- A Dirac-type characterization of \(k\)-chordal graphs
- Title not available (Why is that?)
- Max flows in \(O(nm)\) time, or better
- On rigid circuit graphs
- CLUSTER ALGEBRAS OF FINITE TYPE AND POSITIVE SYMMETRIZABLE MATRICES
- On cyclically orientable graphs
- Triangulated graphs and the elimination process
- Large Induced Subgraphs via Triangulations and CMSO
- Minimal triangulations of graphs: a survey
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Listing all potential maximal cliques of a graph
- Treewidth and minimum fill-in: Grouping the minimal separators
- Finding induced subgraphs via minimal triangulations
- Perfect Elimination and Chordal Bipartite Graphs
- Title not available (Why is that?)
- A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
- Title not available (Why is that?)
- On the semi-perfect elimination
- Characterizations and algorithmic applications of chordal graph embeddings
- Efficient bounds for the stable set, vertex cover and set packing problems
- In-tournament digraphs
- Separability generalizes Dirac's theorem
- Graph extremities defined by search algorithms
- Maximum cardinality search for computing minimal triangulations of graphs
- Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
- An algorithm for fraternal orientation of graphs
- Approximation algorithms for intersection graphs
- Title not available (Why is that?)
- Partial characterizations of 1-perfectly orientable graphs
- \(1\)-perfectly orientable graphs and graph products
- An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs
- Generating weakly triangulated graphs
- Elimination graphs
- Title not available (Why is that?)
- Extremities and orderings defined by generalized graph search algorithms
- Vertex elimination orderings for hereditary graph classes
- Treewidth versus clique number in graph classes with a forbidden structure
- Avoidable paths in graphs
- Avoidable vertices and edges in graphs
- 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs
- AnO(m+nlogn) Algorithm for the Maximum-Clique Problem in Circular-Arc Graphs
- Treewidth versus clique number. I: Graph classes with a forbidden structure
- Shifting paths to avoidable ones
Cited In (5)
Uses Software
This page was built for publication: Avoidable vertices and edges in graphs: existence, characterization, and applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2065802)
