Graph-Theoretic Concepts in Computer Science

DOI10.1007/11604686MaRDI QIDQ5897572zbMATH OpenFDO

Authors Joachim Kneis, Daniel Mölle, Stefan Richter, Peter Rossmanith

Publication date 1 November 2006

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1323192
• scientific article; zbMATH DE number 1031380
• Algorithmic properties of sparse digraphs
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Approximating sparsest cut in graphs of bounded treewidth
• Vertex sparsification in trees
• Computational aspects of treewidth for graph
• scientific article; zbMATH DE number 7310078

Cited in

(19)

• A bound on the pathwidth of sparse graphs with applications to exact algorithms
• scientific article; zbMATH DE number 7310159 (Why is no real title available?)
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• Exact algorithms for exact satisfiability and number of perfect matchings
• On two techniques of combining branching and treewidth
• Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems
• Integrating and sampling cuts in bounded treewidth graphs
• A new upper bound for Max-2-SAT: A graph-theoretic approach
• Solving cut-problems in quadratic time for graphs with bounded treewidth
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• scientific article; zbMATH DE number 7310078 (Why is no real title available?)
• Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
• Trimmed Moebius inversion and graphs of bounded degree
• Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
• Faster algorithms for counting subgraphs in sparse graphs
• Separate, measure and conquer: faster polynomial-space algorithms for Max 2-CSP and counting dominating sets
• \(K_4\)-minor-free induced subgraphs of sparse connected graphs
• Pathwidth of cubic graphs and exact algorithms
• A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach

Describes a project that uses

Uses Software

• MAX-2-SAT

This page was built for publication: Graph-Theoretic Concepts in Computer Science

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