Algorithms for the clique problem with multiple-choice constraints under a series-parallel dependency graph
DOI10.1016/j.dam.2022.09.015zbMath1503.05089OpenAlexW4306855797MaRDI QIDQ2097180
Maximilian Merkert, Andreas Bärmann, Patrick Gemander, Ann-Kathrin Wiertz, F. J. Zaragoza Martínez
Publication date: 11 November 2022
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2022.09.015
integer programmingdynamic programmingseries-parallel graphsclique problemmultiple-choice constraints
Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On finding \(k\)-cliques in \(k\)-partite graphs
- Geometric algorithms and combinatorial optimization
- A partial k-arboretum of graphs with bounded treewidth
- On certain polytopes associated with graphs
- Staircase compatibility and its applications in scheduling and piecewise linearization
- The clique problem with multiple-choice constraints under a cycle-free dependency graph
- Topology of series-parallel networks
- Independent systems of representatives in weighted graphs
- Structural Investigation of Piecewise Linearized Network Flow Problems
- Steiner trees, partial 2–trees, and minimum IFI networks
- Polyhedral Characterization of Discrete Dynamic Programming
- Hall's theorem for hypergraphs
- An Experimental Study of the Treewidth of Real-World Graph Data
- On the facial structure of set packing polyhedra
- Hitting all maximum cliques with a stable set using lopsided independent transversals
- Algorithmic results for potential‐based flows: Easy and hard cases
- Extended formulations in combinatorial optimization
- On the maximum number of cycles in outerplanar and series-parallel graphs
- Parallel algorithms for series parallel graphs and graphs with treewidth two
- Finding all \(k\)-cliques in \(k\)-partite graphs, an application in textile engineering
This page was built for publication: Algorithms for the clique problem with multiple-choice constraints under a series-parallel dependency graph
