Finding minimally weighted subgraphs

DOI10.1007/3-540-53832-1_28MaRDI QIDQ4028099zbMATH OpenFDO

Authors Jürgen Plehn, Bernd Voigt

Publication date 28 March 1993

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

Full work available at URL https://doi.org/10.1007/3-540-53832-1_28

zbMATH Keywords

algorithmminimally weighted subgraphstree-width

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Finding induced trees
• Finding, minimizing, and counting weighted subgraphs
• Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems
• Finding, minimizing, and counting weighted subgraphs
• Graph minors. II. Algorithmic aspects of tree-width

Cited in

(22)

• On problems without polynomial kernels
• A parameterized view on matroid optimization problems
• Are unique subgraphs not easier to find?
• Parameterized complexity of reconfiguration of atoms
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Mining weighted subgraphs in a single large graph
• Maximum weighted induced subgraphs
• scientific article; zbMATH DE number 6866317 (Why is no real title available?)
• Boolean tensor decomposition for conjunctive queries with negation
• On the \(\mathrm{AC}^0\) complexity of subgraph isomorphism
• LATIN 2004: Theoretical Informatics
• A better subgraph of the minimum weight triangulation
• Parameterized Counting and Cayley Graph Expanders
• Parameterized complexity of reconfiguration of atoms
• Finding and counting small tournaments in large tournaments
• Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs. I: Algorithmic results
• Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs. II: Hardness results
• Detecting and counting small subgraphs, and evaluating a parameterized Tutte polynomial: lower bounds via toroidal grids and Cayley graph expanders
• On low tree-depth decompositions
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• Algorithm engineering for color-coding with applications to signaling pathway detection
• Finding induced trees

This page was built for publication: Finding minimally weighted subgraphs

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