The density maximization problem in graphs

DOI10.1007/S10878-012-9465-ZMaRDI QIDQ386420zbMATH OpenOpenAlexFDO

Authors Mong-Jen Kao, Bastian Katz, Marcus Krug, Ignaz Rutter, Dorothea Wagner, Der-Tsai Lee

Publication date 9 December 2013

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://publikationen.bibliothek.kit.edu/1000023123/1978060

zbMATH Keywords

algorithmcomplexitymulti-criteria optimizationsubgraph

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Multi-objective and goal programming (90C29) Programming involving graphs or networks (90C35)

Recommendations

• The density maximization problem in graphs
• Maximum dispersion problem in dense graphs
• On polyhedron graph density in problems of combinatorial optimization
• The Maximum Solution Problem on Graphs
• Density theorems and extremal hypergraph problems
• The densest subgraph problem with a convex/concave size function
• The densest subgraph problem with a convex/concave size function
• Digraph extremal problems, hypergraph extremal problems, and the densities of graph structures
• The densest k-subhypergraph problem
• The densest \(k\)-subhypergraph problem

Cites work

• A linear time algorithm for finding tree-decompositions of small treewidth
• A survey of recent developments in multiobjective optimization
• Algorithms and Computation
• Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence
• An efficient algorithm for the length-constrained heaviest path problem on a tree
• An optimal algorithm for the maximum-density path in a tree
• An Optimal Algorithm for the Maximum-Density Segment Problem
• Color-coding
• Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis.
• Fast algorithms for the density finding problem
• Finding a length-constrained maximum-sum or maximum-density subtree and its application to logistics
• Finding a maximum-density path in a tree under the weight and length constraints
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Graph minors. III. Planar tree-width
• Graph minors. XIII: The disjoint paths problem
• scientific article; zbMATH DE number 432790 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 910922 (Why is no real title available?)
• scientific article; zbMATH DE number 1445376 (Why is no real title available?)
• Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications
• Maintenance of configurations in the plane
• Minimal ratio spanning trees
• On approximating the longest path in a graph
• Priority Search Trees
• Spanning Trees—Short or Small
• The non-approximability of bicriteria network design problems
• The steiner problem in graphs
• Treewidth. Computations and approximations

Cited in

(3)

• On the maximum density of graphs with unique-path labelings
• The density maximization problem in graphs
• Exact and Approximation Algorithms for the Expanding Search Problem

This page was built for publication: The density maximization problem in graphs

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