On the parameterized complexity of the Edge Monitoring problem

Julien Baste; Fairouz Beggas; Hamamache Kheddouci; Ignasi Sau Valls

doi:10.1016/j.ipl.2017.01.008

Homepage
Browse
Search
Deposit
Tools
Stereotypes
HCÉRES report

Journal articles

On the parameterized complexity of the Edge Monitoring problem

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

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 Valls ¹ AuthorId : 190620

Author IdHAL : ignasi-sau ORCID : https://orcid.org/0000-0002-8981-9287

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 metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01487565
Contributor : Ignasi Sau <>
Submitted on : Sunday, March 12, 2017 - 6:33:26 PM
Last modification on : Wednesday, July 8, 2020 - 12:43:51 PM

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 Valls. 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

527

On the parameterized complexity of the Edge Monitoring problem

Identifiers

Collections

Citation

Export

Share

Metrics

527