The clique problem with multiple-choice constraints under a cycle-free dependency graph
DOI10.1016/j.dam.2019.12.015zbMath1446.90132OpenAlexW3001605797WikidataQ126288572 ScholiaQ126288572MaRDI QIDQ2192065
Maximilian Merkert, Patrick Gemander, Andreas Bärmann
Publication date: 29 June 2020
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2019.12.015
Small world graphs, complex networks (graph-theoretic aspects) (05C82) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Perfect graphs (05C17)
Related Items (6)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On finding \(k\)-cliques in \(k\)-partite graphs
- The strong perfect graph theorem
- Alternating orientation and alternating colouration of perfect graphs
- Geometric algorithms and combinatorial optimization
- Staircase compatibility and its applications in scheduling and piecewise linearization
- Review of energy-efficient train control and timetabling
- Nominal and robust train timetabling problems
- Independent systems of representatives in weighted graphs
- A combinatorial algorithm for weighted stable sets in bipartite graphs
- A characterization of perfect graphs
- Structural Investigation of Piecewise Linearized Network Flow Problems
- Instantaneous Power Peak Reduction and Train Scheduling Desynchronization in Subway Systems
- Hall's theorem for hypergraphs
- Reducibility among Combinatorial Problems
- On the facial structure of set packing polyhedra
- Hitting all maximum cliques with a stable set using lopsided independent transversals
- The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
- Finding all \(k\)-cliques in \(k\)-partite graphs, an application in textile engineering
This page was built for publication: The clique problem with multiple-choice constraints under a cycle-free dependency graph