Hamiltonian problems in edge-colored complete graphs and eulerian cycles in edge-colored graphs : some complexity results
From MaRDI portal
Publication:5689636
DOI10.1051/ro/1996300404171zbMath0868.90128OpenAlexW2278255767MaRDI QIDQ5689636
Vangelis Th. Paschos, A. Benkouar, Rachid Saad, Yannis Manoussakis
Publication date: 7 January 1997
Published in: RAIRO - Operations Research (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/105137
NP-completenessedge-colored graphpolynomial characterizationalternating Hamiltonian cyclesalternating factors
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)
Related Items
Some algorithmic results for finding compatible spanning circuits in edge-colored graphs, Paths and trails in edge-colored graphs, Proper Hamiltonian cycles in edge-colored multigraphs, Proper Hamiltonian paths in edge-coloured multigraphs, Parallel connectivity in edge-colored complete graphs: complexity results, Linear amortized time enumeration algorithms for compatible Euler trails in edge-colored graphs, Compatible spanning circuits and forbidden induced subgraphs, Almost Eulerian compatible spanning circuits in edge-colored graphs, Compatible Eulerian circuits in Eulerian (di)graphs with generalized transition systems, Links in edge-colored graphs, Problems from CGCS Luminy, May 2007, Cycles and paths in edge‐colored graphs with given degrees, Paths and Trails in Edge-Colored Graphs, Maximum colored trees in edge-colored graphs, Properly Coloured Cycles and Paths: Results and Open Problems, On s-t paths and trails in edge-colored graphs, Minimal colorings for properly colored subgraphs, Alternating paths in edge-colored complete graphs
