A note on exact algorithms for vertex ordering problems on graphs

DOI10.1007/S00224-011-9312-0zbMath1253.68164OpenAlexW2143693959WikidataQ59567532 ScholiaQ59567532MaRDI QIDQ692902

Hans L. Bodlaender, Arie M. C. A. Koster, Dieter Kratsch, Fedor V. Fomin, Dimitrios M. Thilikos

Publication date: 6 December 2012

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-011-9312-0

zbMATH Keywords

algorithmsgraphsexact algorithmsexponential time algorithmsvertex ordering problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (19)

Improved Parameterized Algorithms for above Average Constraint Satisfaction ⋮ Computing directed pathwidth in \(O(1.89^n)\) time ⋮ On the Equivalence among Problems of Bounded Width ⋮ Treewidth and pathwidth parameterized by the vertex cover number ⋮ Rank-width: algorithmic and structural results ⋮ On exact algorithms for the permutation CSP ⋮ Characterizations and directed path-width of sequence digraphs ⋮ Strong SDP based bounds on the cutwidth of a graph ⋮ On integer linear programs for treewidth based on perfect elimination orderings ⋮ Minimal NMR distance information for rigidity of protein graphs ⋮ Computing the pathwidth of directed graphs with small vertex cover ⋮ Computing tree-depth faster than \(2^n\) ⋮ On distance-preserving elimination orderings in graphs: complexity and algorithms ⋮ Linear ordering based MIP formulations for the vertex separation or pathwidth problem ⋮ Unnamed Item ⋮ Positive-Instance Driven Dynamic Programming for Treewidth. ⋮ Finding small-width connected path decompositions in polynomial time ⋮ Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth ⋮ Exact algorithms for intervalizing coloured graphs

Cites Work

• Unnamed Item
• The vertex separation number of a graph equals its path-width
• Some simplified NP-complete graph problems
• A partial k-arboretum of graphs with bounded treewidth
• Fugitive-search games on graphs and related parameters
• Finding Induced Subgraphs via Minimal Triangulations
• A Dynamic Programming Approach to Sequencing Problems
• Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In
• Exact Algorithms for Treewidth and Minimum Fill-In
• Computing Pathwidth Faster Than 2 n
• Expected Computation Time for Hamiltonian Path problem
• On Exact Algorithms for Treewidth
• Automata, Languages and Programming
• Heuristic and metaheuristic methods for computing graph treewidth

This page was built for publication: A note on exact algorithms for vertex ordering problems on graphs