On the parameterized complexity of the Edge Monitoring problem

Julien Baste; Fairouz Beggas; Hamamache Kheddouci; Ignasi Sau

Homepage
Browse
Search
Deposit
Tools
Idées reçues...
HCÉRES report

On the parameterized complexity of the Edge Monitoring problem

Julien Baste ¹ Fairouz Beggas ² Hamamache Kheddouci ^{3, 2} Ignasi Sau ¹

1 ALGCO - Algorithmes, Graphes et Combinatoire

LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier

2 GOAL - Graphes, AlgOrithmes et AppLications

LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information

3 GrAMA - Graphes, Algorithmes et Multi-Agents

LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information

Julien Baste ¹ AuthorId : 881041

Author IdHAL : baste

Fairouz Beggas ² AuthorId : 1509432
Author

Hamamache Kheddouci ^{3, 2} AuthorId : 206969

Author IdHAL : hamamache-kheddouci

Ignasi Sau ¹ AuthorId : 190620

Author IdHAL : ignasi-sau

1 ALGCO - Algorithmes, Graphes et Combinatoire (France) StructId : 388229

LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (161 rue Ada - 34095 Montpellier - France) StructId : 181
- UM - Université de Montpellier : UMR5506 (163 rue Auguste Broussonnet - 34090 Montpellier - France) StructId : 410122
- CNRS - Centre National de la Recherche Scientifique : UMR5506 (France) StructId : 441569

2 GOAL - Graphes, AlgOrithmes et AppLications (France) StructId : 413088

LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information (Bâtiment Blaise Pascal - 20, avenue Albert Einstein - 69621 Villeurbanne cedex - France) StructId : 2003
- UL2 - Université Lumière - Lyon 2 (86, rue Pasteur - 69007 Lyon - France) StructId : 33804
- ECL - École Centrale de Lyon (36 avenue Guy de Collongue - 69134 Ecully cedex - France) StructId : 126765
  - Université de Lyon (92 rue Pasteur - CS 30122, 69361 Lyon Cedex 07 - France) StructId : 301088
- UCBL - Université Claude Bernard Lyon 1 (43, boulevard du 11 novembre 1918, 69622 Villeurbanne cedex - France) StructId : 194495
  - Université de Lyon (92 rue Pasteur - CS 30122, 69361 Lyon Cedex 07 - France) StructId : 301088
- CNRS - Centre National de la Recherche Scientifique : UMR5205 (France) StructId : 441569
- INSA Lyon - Institut National des Sciences Appliquées de Lyon (20 Avenue Albert Einstein, 69621 Villeurbanne cedex - France) StructId : 219748
  - Université de Lyon (92 rue Pasteur - CS 30122, 69361 Lyon Cedex 07 - France) StructId : 301088
  - INSA - Institut National des Sciences Appliquées (France) StructId : 301232

3 GrAMA - Graphes, Algorithmes et Multi-Agents (France) StructId : 392150

LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information (Bâtiment Blaise Pascal - 20, avenue Albert Einstein - 69621 Villeurbanne cedex - France) StructId : 2003
- UL2 - Université Lumière - Lyon 2 (86, rue Pasteur - 69007 Lyon - France) StructId : 33804
- ECL - École Centrale de Lyon (36 avenue Guy de Collongue - 69134 Ecully cedex - France) StructId : 126765
  - Université de Lyon (92 rue Pasteur - CS 30122, 69361 Lyon Cedex 07 - France) StructId : 301088
- UCBL - Université Claude Bernard Lyon 1 (43, boulevard du 11 novembre 1918, 69622 Villeurbanne cedex - France) StructId : 194495
  - Université de Lyon (92 rue Pasteur - CS 30122, 69361 Lyon Cedex 07 - France) StructId : 301088
- CNRS - Centre National de la Recherche Scientifique : UMR5205 (France) StructId : 441569
- INSA Lyon - Institut National des Sciences Appliquées de Lyon (20 Avenue Albert Einstein, 69621 Villeurbanne cedex - France) StructId : 219748
  - Université de Lyon (92 rue Pasteur - CS 30122, 69361 Lyon Cedex 07 - France) StructId : 301088
  - INSA - Institut National des Sciences Appliquées (France) StructId : 301232

Keywords : FPT algorithm Parameterized complexity Bidimensionality Theory Edge Monitoring Graph algorithms

Document type :

Journal articles

Domain :

Mathematics [math]

Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01487565
Contributor : Ignasi Sau <>
Submitted on : Sunday, March 12, 2017 - 6:33:26 PM
Last modification on : Friday, June 14, 2019 - 10:32:53 AM

Identifiers

HAL Id : lirmm-01487565, version 1
DOI : 10.1016/j.ipl.2017.01.008

Collections

Citation

Julien Baste, Fairouz Beggas, Hamamache Kheddouci, Ignasi Sau. On the parameterized complexity of the Edge Monitoring problem. Information Processing Letters, Elsevier, 2017, 121, pp.39-44. ⟨10.1016/j.ipl.2017.01.008⟩. ⟨lirmm-01487565⟩

On the parameterized complexity of the Edge Monitoring problem

Identifiers

Collections

Citation

Export

Metrics

419

Contact

On the parameterized complexity of the Edge Monitoring problem

Identifiers

Collections

Citation

Export

Share

Metrics

419

Contact