A note on exact algorithms for vertex ordering problems on graphs
DOI10.1007/S00224-011-9312-0zbMATH Open1253.68164OpenAlexW2143693959WikidataQ59567532 ScholiaQ59567532MaRDI QIDQ692902FDOQ692902
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)
Full work available at URL: https://doi.org/10.1007/s00224-011-9312-0
Recommendations
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)
Cites Work
- A Dynamic Programming Approach to Sequencing Problems
- A partial k-arboretum of graphs with bounded treewidth
- On Exact Algorithms for Treewidth
- Some simplified NP-complete graph problems
- The vertex separation number of a graph equals its path-width
- Fugitive-search games on graphs and related parameters
- Finding induced subgraphs via minimal triangulations
- Exact Algorithms for Treewidth and Minimum Fill-In
- Computing Pathwidth Faster Than 2 n
- A space-time tradeoff for permutation problems
- Expected Computation Time for Hamiltonian Path problem
- Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In
- Automata, Languages and Programming
- Heuristic and metaheuristic methods for computing graph treewidth
Cited In (27)
- On exact algorithms for the permutation CSP
- Exact algorithms for intervalizing coloured graphs
- Vertex ordering with optimal number of adjacent predecessors
- Minimal NMR distance information for rigidity of protein graphs
- On distance-preserving elimination orderings in graphs: complexity and algorithms
- Improved parameterized algorithms for above average constraint satisfaction
- Computing directed pathwidth in \(O(1.89^n)\) time
- Characterizations and directed path-width of sequence digraphs
- On the approximability of digraph ordering
- Finding small-width connected path decompositions in polynomial time
- On integer linear programs for treewidth based on perfect elimination orderings
- Strong SDP based bounds on the cutwidth of a graph
- An order approach for the core maintenance problem on edge-weighted graphs
- Optimal vertex ordering of graphs
- Linear ordering based MIP formulations for the vertex separation or pathwidth problem
- Computing the pathwidth of directed graphs with small vertex cover
- Rank-width: algorithmic and structural results
- Ordering transactions with bounded unfairness: definitions, complexity and constructions
- Treewidth and pathwidth parameterized by the vertex cover number
- Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
- On the equivalence among problems of bounded width
- Computing tree-depth faster than \(2^n\)
- A space-time tradeoff for permutation problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- The referenced vertex ordering problem: theory, applications, and solution methods
- Positive-instance driven dynamic programming for treewidth
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)
