On distance-preserving elimination orderings in graphs: complexity and algorithms

DOI10.1016/j.dam.2018.02.007zbMath1387.05062OpenAlexW2791305880WikidataQ130084617 ScholiaQ130084617MaRDI QIDQ1752455

Nicolas Nisse, Guillaume Ducoffe, Mauricio Soto, David Coudert

Publication date: 24 May 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-01741277/file/dpo-hal.pdf

zbMATH Keywords

NP-completenessinteger linear programmingexact exponential algorithmbounded treewidthmetric graph theorydistance-preserving elimination ordering

Mathematics Subject Classification ID

Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items

First-order logic axiomatization of metric graph theory

Uses Software

• SageMath
• CPLEX

Cites Work

• Discretization vertex orders in distance geometry
• A note on exact algorithms for vertex ordering problems on graphs
• A non-shellable 3-sphere
• Distance-hereditary graphs
• Homogeneously orderable graphs
• A simple linear time algorithm for cograph recognition
• On the semi-perfect elimination
• Vertex-to-vertex pursuit in a graph
• Tandem-win graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number
• Cop and Robber Games When the Robber Can Hide and Ride
• Algorithmic Aspects of Vertex Elimination on Graphs
• On Distance-Preserving and Domination Elimination Orderings
• Dually Chordal Graphs
• The complexity of theorem-proving procedures
• To Approximate Treewidth, Use Treelength!
• Recognition of collapsible complexes is NP-complete
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item