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

zbMATH Keywords

schedulingperfect graphclique problemmultiple-choice constraintsconvex-hull description

Mathematics Subject Classification ID

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)

The Bipartite Boolean Quadric Polytope with Multiple-Choice Constraints ⋮ EETTlib—Energy‐efficient train timetabling library ⋮ Energy-efficient timetabling in a German underground system ⋮ Set characterizations and convex extensions for geometric convex-hull proofs ⋮ On recognizing staircase compatibility ⋮ Algorithms for the clique problem with multiple-choice constraints under a series-parallel dependency graph

Uses Software

• Gurobi

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