Graph-Theoretic Concepts in Computer Science

DOI10.1007/11604686zbMATH Open1171.05428MaRDI QIDQ5897572FDOQ5897572

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)

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

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)

Cited In (20)

• A bound on the pathwidth of sparse graphs with applications to exact algorithms
• Title not available (Why is that?)
• On sparsification for computing treewidth
• 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
• Title not available (Why is that?)
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• 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

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)