A note on exact algorithms for vertex ordering problems on graphs

DOI10.1007/S00224-011-9312-0MaRDI QIDQ692902zbMATH OpenOpenAlexWikidataFDO

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

Publication date 6 December 2012

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

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

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

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

Recommendations

• Optimal vertex ordering of graphs
• The referenced vertex ordering problem: theory, applications, and solution methods
• A space-time tradeoff for permutation problems
• scientific article; zbMATH DE number 1953201
• Computing and Combinatorics

Cites work

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

Cited in

(26)

• Rank-width: algorithmic and structural results
• Computing tree-depth faster than \(2^n\)
• Optimal vertex ordering of graphs
• On integer linear programs for treewidth based on perfect elimination orderings
• On exact algorithms for the permutation CSP
• Characterizations and directed path-width of sequence digraphs
• Treewidth and pathwidth parameterized by the vertex cover number
• Linear ordering based MIP formulations for the vertex separation or pathwidth problem
• Strong SDP based bounds on the cutwidth of a graph
• Vertex ordering with optimal number of adjacent predecessors
• Graph and string parameters: connections between pathwidth, cutwidth and the locality number
• Positive-instance driven dynamic programming for treewidth
• Improved parameterized algorithms for above average constraint satisfaction
• The referenced vertex ordering problem: theory, applications, and solution methods
• An order approach for the core maintenance problem on edge-weighted graphs
• Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
• Exact algorithms for intervalizing coloured graphs
• scientific article; zbMATH DE number 1560506 (Why is no real title available?)
• Ordering transactions with bounded unfairness: definitions, complexity and constructions
• Finding small-width connected path decompositions in polynomial time
• On the equivalence among problems of bounded width
• Minimal NMR distance information for rigidity of protein graphs
• A space-time tradeoff for permutation problems
• On distance-preserving elimination orderings in graphs: complexity and algorithms
• Computing directed pathwidth in \(O(1.89^n)\) time
• Computing the pathwidth of directed graphs with small vertex cover

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

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